题目
{% fold 点击显/隐题目 %}
这里4*4的方格中每一格表示进入这个房间时,队员可以向右或向下穿过的房间数。
郑恺是奔跑小王子,当他拿到这张地图时,脸都变绿了,速度再快,进了迷宫一样的房间也是没办法啊,还好参加JSOI2015夏令营的小伙伴都在,你能帮帮他算出从左上角可以到达右下角的路径数目吗?
题解
题意理解如下:每个方格的数字代表向右/下移动的格数(不能转向)
因此有 f(x,y)=f(x+Map[x][y],y)+f(x,y+Map[x][y])
采用记忆化搜索递推即可
代码
{% fold 点击显/隐代码 %}```cpp 又是迷宫 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
//
#define debug
#include
//
#include
#include
#include
using namespace std;
const int maxn = 105;
int Map[maxn][maxn];
int ans[maxn][maxn];
bool vis[maxn][maxn];
int n;
int dfs(int x, int y) {
if (x > n || y > n)
return 0;
if (ans[x][y] == -1) {
ans[x][y] = 0;
if (x + Map [x][y] <= n)
ans[x][y] += dfs(x + Map [x][y], y);
if (y + Map [x][y] <= n)
ans[x][y] += dfs(x, y + Map [x][y]);
}
return ans[x][y];
}
int main() {
#ifdef debug
freopen("in.txt", "r", stdin);
int START = clock();
#endif
cin.tie(0);
cin.sync_with_stdio(false);
while (cin >> n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> Map[i][j];
}
}
memset(ans, -1, sizeof(ans));
ans[n][n] = 1;
cout << dfs(1, 1) << endl;
// for (int i = 1; i <= n; i++) {
// for (int j = 1; j <= n; j++) {
// cout << ans[i][j];
// }
// cout << endl;
// }
}
#ifdef debug
printf("Time:%.3fs.\n", double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
}
{% endfold %}