2018 SCNUACM 校赛 D题: Escape from

先附上题目描述：

题目描述
WWJ loves his girlfriend very much. Suppose one day he stuck in a maze and could not see his
girlfriend. The lost case upsets him so much. WWJ wants to escape the maze as soon as possible.
However, he is very sleepy due to the overnight work, so in a certain position, he will stop and take a
nap. To simplify this problem, the maze can be considered an N × M two-dimensional array while WWJ
starts at (0, 0) (upper left)and the exit is in (N − 1, M − 1) (lower right ). The elements in array are consist
of . , X and number T range from 1-9.
The following rules describe how WWJ moves in maze.

1. He takes 1 minute to move from one position to another.
2. He can only move in four directions (up, down, left, right) at each step.
3. He cannt pass the position marked by X because it represents the walls.
4. When he reaches the position with number T, he will fall asleep in the next T minutes.
   Can you write a program to help him calculate the least time he takes to escape from this maze?
   输入
   The input contains several test cases. Each test case starts with a line contains two numbers N and M
   (2 >≤ N ≤ 100; 2 ≤ M ≤ 100) which indicate the size of the maze. Then an N × M two-dimensional array
   follows, which describe the whole maze. The input is terminated by the end of file. More details in the
   Sample Input.
   输出
   For each test case, you should output the least time WWJ should take to escape from the maze.
   If WWJ cannot help himself, please output: 'God please help our poor wwj.' .
   样例输入
   5 6
   .XX.1.
   ..X.2.
   2...X.
   ...XX.
   XXXXX.
   5 6
   .XX...
   ..XX1.
   2...X.
   ...XX.
   XXXXX.
   样例输出
   13
   God please help our poor wwj.

看到Maze这个关键字眼很容易想到BFS求最短路（可能是Leosu最近写多了BFS，所以看什么都是BFS，捂脸），事实上还真是BFS，于是很容易套模板写出来，不过这里我们需要注意一个地方就是这里求的是最少时间，也就是每一个点不一定只遍历一遍！！！所以用bool visit[][]来判重是有问题的。我们仔细分析题目可以看出这道题有种背包问题的感觉，因为每个点都有一个对应的最短到达时间，所以我们联想到状态转移方程，每到一个点都判断到这个点的时间是否比当前点的最短时间少，是才继续走。所以我们可以利用int visit[][]来存每一个点的最小时间最后输出visit[N-1][M-1]点的时间即可。
话不多说（虽然已经说了不少。。），直接上AC代码：

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#define tx (x+dx[i])
#define ty (y+dy[i])
#define MAXN (100+10)
using namespace std;
struct temp{
    int x;
    int y;
    int cnt;
}a,b,c;
char maze[MAXN][MAXN];
int visit[MAXN][MAXN];
int n,m,dx[] = {-1,1,0,0},dy[] = {0,0,-1,1};
queue<struct temp>q;

bool check(int x,int y){
    if(x>=0&&y>=0&&x<n&&y<m) return true;
    return false;
}

void BFS(){
    a.x = 0,a.y = 0,a.cnt = 0;
    q.push(a);
    while(!q.empty()){
        int x,y;
        a = q.front();
        x = a.x,y = a.y;
        for(int i = 0;i<4;i++){
            if(check(tx,ty)&&maze[tx][ty]!='X'){
                if(maze[tx][ty]=='.'){
                    b.cnt = a.cnt+1;
                }
                else{
                    b.cnt = a.cnt+(int)(maze[tx][ty]-'0')+1;
                }
                if(b.cnt>=visit[tx][ty])//****关键代码，进行判重，注意要>=因为只是>的话只要出现数据全是'.'的大图就会出现TLE（超时）
                    continue;
                b.x = tx,b.y = ty;
                visit[tx][ty] = b.cnt;
                q.push(b);
            }
        }
        q.pop();
    }
}

int main()
{
    //freopen("text.txt","r",stdin);
    while(cin>>n>>m){
        for(int i = 0;i<n;i++){
            scanf("%s",maze[i]);
            for(int j = 0;j<m;j++){
                visit[i][j] = 99999999;
            }
        }
        BFS();
        if(visit[n-1][m-1]!=99999999){
            printf("%d\n",visit[n-1][m-1]);
        }
        else{
            printf("God please help our poor wwj.\n");
        }
    }
    return 0;
}