[学習記録]AtCoder EDP H-Grid-1[Go]

問題

縦H 行、横 W 列のグリッドがあります。 上から i 行目、左から j 列目のマスを (i,j) で表します。

各 i,j (1≤i≤H, 1≤j≤W) について、マス (i,j) の情報が文字 ai,j​ によって与えられます。 ai,j​ が . ならばマス (i,j) は空マスであり、ai,j​ が # ならばマス (i,j) は壁のマスです。 マス (1,1)(1,1) および (H,W) は空マスであることが保証されています。

太郎君は、マス (1,1)(1,1) から出発し、右または下に隣り合う空マスへの移動を繰り返すことで、マス (H,W) まで辿り着こうとしています。

マス (1,1)(1,1) から (H,W) までの太郎君の経路は何通りでしょうか？ 答えは非常に大きくなりうるので、10＾9+7 で割った余りを求めてください。

解法

マス (i, j)に移動できるのは
・マス ( i -1, j)　（上からの移動）
・マス ( i, j -1)　（左からの移動）
のみとなっているので、各i, jについて上記を計算する。
壁の場合は通ることができないのでゼロになる

// あとで取り出しやすいようにスライスで保持
sli := make([][]string, h)
for i := 0; i < h; i++ {
	sli[i] = strings.Split(read(), "")
}

for i := 1; i <= h; i++ {
	dp[i] = make([]int, w+1)
	for j := 1; j <= w; j++ {
		if sli[i-1][j-1] == "." {
            // 道
     		dp[i][j] = (dp[i-1][j] + dp[i][j-1])
		} else {
            // 壁
			dp[i][j] = 0
		}
	}
}

マス(1, 1)は空マス確定であり、そこへ行く経路は１となる（dp[1][1] = 1)
そうなるように、dpに初期値を設定する
（dp[0][1]に１を設定することで、ループ内で分岐をせずとも各々の操作が可能になる）

dp := make([][]int, h+1)
dp[0] = make([]int, w+1)
dp[0][1] = 1

> (loop start)
> dp[1][1] = dp[0][1] + dp[1][0] = 1 + 0 = 1

出力は10 ^ 9 + 7で割ったあまりを出す必要がある。
そのため、dpに値を入れる時に余りをとる。
（最後に余りをとると、途中の計算時にオーバーフローしてしまう場合がある）

// 道
dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % prime_number

コード（AC）

func run() interface{} {
	h, w := readInt(), readInt()

	sli := make([][]string, h)
	for i := 0; i < h; i++ {
		sli[i] = strings.Split(read(), "")
	}

	dp := make([][]int, h+1)
	dp[0] = make([]int, w+1)
	dp[0][1] = 1
	for i := 1; i <= h; i++ {
		dp[i] = make([]int, w+1)
		for j := 1; j <= w; j++ {
			if sli[i-1][j-1] == "." {
                // 道
				dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % prime_number
			} else {
                // 壁
				dp[i][j] = 0
			}
		}
	}

	ans := dp[h][w]
	return ans
}