题目

{% 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
{% endfold %}

题解

题意理解如下：每个方格的数字代表向右/下移动的格数（不能转向）
因此有 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 %}