e581 - 11067 - Little Red Riding Hood
題目描述
題目描述了小紅帽前往祖母家的路徑規劃問題。地圖是一個矩形網格，小紅帽從左下角出發，祖母家在右上角。小紅帽只能向右或向上移動。題目給定了狼可能出現的位置，小紅帽需要計算在避開狼的前提下，從家到祖母家的路徑數量。
解題思路
本題可以使用動態規劃 (Dynamic Programming) 解決。定義 dp[i][j] 為到達網格點 (i, j) 的路徑數量。初始化 dp[1][1] = 1，因為從起點 (0, 0) 到 (1, 1) 只有一條路徑。然後，對於每個網格點 (i, j)，如果該點沒有狼，則路徑數量等於從上方 (i-1, j) 和左方 (i, j-1) 到達該點的路徑數量之和，即 dp[i][j] = dp[i-1][j] + dp[i][j-1]。如果該點有狼，則 dp[i][j] = 0。最後，dp[n][m] 即為到達祖母家的路徑數量。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 和 m 分別是地圖的寬度和高度。需要遍歷整個網格。
- 空間複雜度: O(n*m)，用於儲存
dp陣列。
程式碼
#include <iostream>
using namespace std;
long long dp[105][105],n,x,y,m,k,a[105][105];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(cin >> n >> m){
if(n==0&&m==0)break;
cin >> k;
++n;
++m;
for(int i=0;i<=n;++i){
for(int j=0;j<=m;++j){
dp[i][j]=a[i][j]=0;
}
}
dp[1][1]=1;
for(int i=0;i<k;++i){
cin >> x >> y;
++x;
++y;
a[x][y]=1;
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(a[i][j]){
dp[i][j]=0;
}
else{
dp[i][j]+=dp[i-1][j]+dp[i][j-1];
}
}
}
if(dp[n][m]==0){
cout << "There is no path.\n";
}
else if(dp[n][m]==1){
cout << "There is one path from Little Red Riding Hood's house to her grandmother's house.\n";
}
else{
cout << "There are " << dp[n][m] << " paths from Little Red Riding Hood's house to her grandmother's house.\n";
}
}
}