題意#
給定一個大小為 \( n \times n \) 的方格地圖，地圖上是由 .（安全通道）和 *（陷阱）組成的。
你現在站在左上角，每一次只能選擇向右或向下移動一格，而且過程中絕對不能踩到陷阱。你的任務是計算出：總共有多少種不同的路線，可以讓你安全抵達右下角的終點？
因為路線數量可能會很大，答案需要對 \( 10^9 + 7 \) 取餘數。
思路#
這是非常基礎的二維動態規劃題，網格路徑問題的最佳入門款。
我們可以建立一個大小為 \( (n+1) \times (n+1) \) 的二維陣列 dp，其中 dp[i][j] 就代表「走到第 i 列、第 j 行這個格子的所有合法路線數量」。
（把陣列開大一點是為了方便處理邊界條件，這樣我們就不用寫一堆判斷去檢查是不是在邊緣地帶，越界的地方預設會是 0，不會影響加總）。
因為我們只能往右或往下走，所以對於地圖上任何一個格子 (i, j)，我們只可能從它的「上方 (i-1, j)」或是「左方 (i, j-1)」走過來。
也就是說，如果目前這個格子不是陷阱，那麼走到這裡的方法數 dp[i][j]，就等於「走到上方的路線數」加上「走到左方的路線數」。
如果目前這格剛好是陷阱 *，那就代表這條路死胡同了，不用去管它，維持 0 即可。
透過這樣一層一層把數字加起來，最後一路加到右下角，就是我們要的答案。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
signed main() { WA();
int n, p = 1e9+7; cin >> n;
// v 用來儲存地圖輸入資料
vector<vector<char>> v(n, vector<char>(n));
// dp 陣列開 n+1 大小，1-based indexing，方便處理邊界（第 0 列與第 0 行全為 0）
vector<vector<int>> dp(n+1, vector<int>(n+1));
// 讀取地圖，若起點不是陷阱，代表走到起點的方法數為 1
for (auto &i : v) for (auto &j : i) cin >> j;
dp[1][1] = v[0][0] == '.';
// 開始從左上角推廣到右下角
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
// v 的索引是 0-based，所以要用 i-1 跟 j-1 去查地圖
if (v[i-1][j-1] != '*') {
// 如果不是陷阱，抵達這格的方法數 = 來自上方的數量 + 來自左方的數量
dp[i][j] += (dp[i-1][j] + dp[i][j-1]) % p;
}
}
}
cout << dp[n][n] << '\n';
}
