这是一篇最后编辑于 8 年前 的文章，其内容可能与目前实际情况差异较大，请注意甄别
题目
{% fold 点击显/隐题目 %}
Description 晚上，跑男们来了节目的最后一站：江苏省扬州中学，完成最后一项比赛：撕名牌。撕名牌的地点是一个由n\*n房间组成的正方形，每个房间里都有一个数字，表示从这个房间可以通过地道向右或向下穿过几个房间。从左上角开始，如果谁能安全到达右下角就算胜利。
这里4*4的方格中每一格表示进入这个房间时，队员可以向右或向下穿过的房间数。
郑恺是奔跑小王子，当他拿到这张地图时，脸都变绿了，速度再快，进了迷宫一样的房间也是没办法啊，还好参加JSOI2015夏令营的小伙伴都在，你能帮帮他算出从左上角可以到达右下角的路径数目吗？
第一行为一个整数n，表示棋盘的大小。 以下有n行，每行有n个数字（数字与数字之间有一个空格隔开），表示在相应的格子内，棋子可以向右或向下跳跃的格子数。
输出共一行，包含一个数，表示从左上角可以到达右下角的路径数目。
4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0
3
题解
题意理解如下：每个方格的数字代表向右/下移动的格数（不能转向）
因此有 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 %}