AOJ 887.又是迷宫

146


题目



点击显/隐题目

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])
采用记忆化搜索递推即可


代码


点击显/隐代码
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <cstring>
#include <iostream>
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;
}
发布评论
  • 点击查看/关闭被识别为广告的评论