Controls
Masukkan labirin. Setiap baris adalah satu baris petak (. = aman, * = perangkap).
Jumlah jalur: 3 (mod 10^9+7)
Deskripsi
Bearcu menemukan labirin bawah tanah n x n. Beberapa
petak berisi lubang perangkap (*). Ia hanya bisa bergerak
ke kanan atau ke bawah.
Tugas: hitung jumlah jalur berbeda dari pojok kiri atas ke pojok kanan bawah.
Algoritma DP
dp[r][c]= jumlah jalur sampai sel (r,c)dp[0][0] = 1dp[r][c] = dp[r-1][c] + dp[r][c-1](mod M)- Sel perangkap:
dp[r][c] = 0
Tautan Soal
DP Grid
| 1 | 1 | 1 | 1 |
| 1 | * | 1 | 2 |
| 1 | 1 | 2 | * |
| * | 1 | 3 | 3 |