AtCoder Beginner Contest 037 D - 経路

問題

abc037.contest.atcoder.jp

解法

dp の本質は DAG って話を思い出せば簡単に解けます。
d.hatena.ne.jp

この問題では, あるマスから遷移できるマスは一方通行的なので, DAG であると考えることができます。その上での経路数はまさに上の記事の言っている dp です。

const int MOD = 1e9+7;
const int MAX = 1111;
int H, W;
int board[MAX][MAX];

ll dp[MAX][MAX];

bool inRange(int y, int x) {
	return 0 <= y && y < H && 0 <= x && x < W;
}

ll dfs(int y, int x) {
	ll& ret = dp[y][x];
	if (ret >= 0) return ret;
	ret = 1;
	for (int i = 0; i < 4; i++) {
		int ny = y+dy[i], nx = x+dx[i];
		if (inRange(ny, nx) && board[y][x] < board[ny][nx]) {
			(ret += dfs(ny, nx)) %= MOD;
		}
	}
	return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> H >> W;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++)
    	cin >> board[i][j];
    memset(dp, -1, sizeof(dp));
    ll ans = 0;
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) {
    	(ans += dfs(i, j)) %= MOD;
    }
    cout << ans << endl;
    return 0;
}