- 問題描述
- 輸入格式
- 輸出格式
- 樣例
- 代碼
- 補充
題解分析等閑了就補上(doge)，慢慢更新ing
路徑計數
比較經典常見的動態規劃dp題目了
問題描述
有一個n×n的網格，有些格子是可以通行的，有些格子是障礙，
一開始你在左上角的位置，你可以每一步往下或者往右走，問有多少種走到右下角的方案，
由于答案很大，輸出對1e9+7取模的結果，
輸入格式
第一行一個正整數n，
接下來n行，每行n個正整數，1表示可以通行，0表示不能通行，
輸出格式
一個整數，表示答案，
樣例輸入
3
1 1 1
1 0 1
1 1 1樣例輸出
2代碼
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int main()
{
int a, n;
scanf("%d", &n);
bool is[105][105];
int f[105][105];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
scanf("%d", &is[i][j]);
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(!is[i][j])
f[i][j] = 0;
else {
if(i == 1 && j == 1) {
f[i][j] = 1;
continue;
}
if(i == 1 && j != 1) {
f[i][j] = f[i][j - 1];
continue;
}
if(i != 1 && j == 1) {
f[i][j] = f[i - 1][j];
continue;
}
f[i][j] = (f[i - 1][j] % mod + f[i][j - 1] % mod) % mod;
}
}
}
printf("%d", f[n][n]);
return 0;
}補充
求余運算規則：
設正整數x，y，p，求余符號為%，
對于加法運算：(x + y) % p = (x % p + y % p) % p
對于乘法運算：(x * y) % p = [(x % p) * (y % p)] % p
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/440405.html
標籤：其他
下一篇：資料結構 - 堆