学步园

500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^_^。

突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他知道公主在迷宫中还能坚持T天，他急忙赶到迷宫，开始到处寻找公主的下落。
时间一点一点的过去，Jesse还是无法找到公主。最后当他找到公主的时候，美丽的公主已经死了。从此Jesse郁郁寡欢，茶饭不思，一年后追随公主而去了。T_T
500年后的今天，Jesse托梦给你，希望你帮他判断一下当年他是否有机会在给定的时间内找到公主。

他会为你提供迷宫的地图以及所剩的时间T。请你判断他是否能救出心爱的公主。

题目包括多组测试数据。
每组测试数据以三个整数N,M,T(0 < N,M <= 20)开头，
分别代表迷宫的长和高，以及公主能坚持的天数。
紧接着有M行，N列字符，由"."，"*"，"P"，"S"组成。其中
"." 代表能够行走的空地。
"*" 代表墙壁，Jesse不能从此通过。
"P" 是公主所在的位置。
"S" 是Jesse的起始位置。
每个时间段里Jesse只能选择“上、下、左、右”任意一方向走一步。
输入以0 0 0结束。

如果能在规定时间内救出公主输出“YES”，否则输出“NO”。

4 4 10
....
....
....
S**P
0 0 0

YES

陆泽西

——————————————————————分割线——————————————————————

思路：这是我做的第一道BFS题目，说实话刚开始理解起来蛮不容易的，结构并不复杂，即展开一个结点周围需要访问的结点，按照一定顺序和条件进入队列，队列按照先进先出的原则，遍历整个图内所有结点，所以每一步，只在一个结点处同时访问其周围结点，并且只有该结点处理完毕后才能出队。走迷宫正是如此，到达当前位置后，同时向四个方向访问，直到找到公主。

代码如下：

#include <stdio.h>
#include <memory.h>
int mat[30][30], vis[30][30], dis[30][30];//用mat数组储存迷宫状态;用vis数组作访问标记；用dis标记当前位置离起点最短距离
int que[900], l, r, sx, sy, ox, oy;        //用que建立队列，该队列每次进入一个已访问位置
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};//数组dx,dy表示当前位置下标向上下左右偏移
char s[30];
int bfs(int x, int y){
    int fron = 0, rear = 0;                //fron表示队首，rear记录队尾
    int d, u = x * r + y;                  //u记录当前位置下标（压缩状态）
    vis[x][y] = 1;
    dis[x][y] = 0;
    que[rear++] = u;			   //起点入队，队尾指针后移
    while(fron < rear){                    //在队列为空之前，一直循环下去，直到完全遍历
        u = que[fron++] ;                  //u替换为当前队列首位元素
        x = u / r;
        y = u % r;                              
        for(d = 0; d < 4; d++){
            int nx = x + dx[d], ny =  y + dy[d];//当前位置偏移
            if(nx >= 0 && nx < l && ny >=0 && ny < r && mat[nx][ny] && !vis[nx][ny]){
                int v = nx * r + ny;        //判断偏移后的当前位置，未访问且为1，则储存位置
                que[rear++] = v;            //当前位置进队
                vis[nx][ny] = 1;
                dis[nx][ny] = dis[x][y] + 1;//当前位置的最短距离比上次最短距离多1
                if(nx == ox&&ny == oy)//走到终点，则返回终点位置的dis
                    return dis[nx][ny];
            }
        }
    }
    return -1;                              //找不到终点，返回负值
}
int main(){
    int ti, tim_li;
    int i, j;
    while(scanf("%d%d%d", &r, &l, &tim_li) != EOF&&(l||r||tim_li)){
        memset(mat, 0, sizeof(mat));	    //清空迷宫状态及其访问状态
        memset(vis, 0, sizeof(vis));
        for(i = 0; i < l; i++){
            scanf("%s", s);		    //按行输入迷宫地图，按行转化
            for(j = 0; j < r; j++){
                switch(s[j]){
                    case 'S':mat[i][j] = 1;sx = i; sy = j; break;
                    case 'P':mat[i][j] = 1;ox = i; oy = j; break;//注意！倘若公主所在位置不标记为1,永远都找不到公主
                    case '.':mat[i][j] = 1; break;//走得通为1
                    case '*':mat[i][j] = 0; break;//墙壁为0
                }
            }
        }
        ti = bfs(sx, sy);
        if(ti == -1)
        printf("NO\n");
        else
        printf("%s\n", (ti > tim_li ? "NO" : "YES"));
    }
    return 0;
}