// Latihan bergaya OSN, Bab 13, soal 1 -- pembahasan. // // dp[i][j] = banyaknya jalur dari pojok kiri atas ke petak (i, j). // Sebuah petak hanya bisa dicapai dari atas atau dari kiri. #include #include #include using namespace std; int main() { int r, c; cin >> r >> c; vector peta(r); for (int i = 0; i < r; i++) cin >> peta[i]; vector> dp(r, vector(c, 0)); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (peta[i][j] == '#') { dp[i][j] = 0; continue; } if (i == 0 && j == 0) { dp[i][j] = 1; continue; } long long total = 0; if (i > 0) total += dp[i - 1][j]; if (j > 0) total += dp[i][j - 1]; dp[i][j] = total; } } cout << dp[r - 1][c - 1] << "\n"; return 0; }