Gym - 100947H Phobia

题目大意

其实就是一个女孩面对蟑螂扩张的威胁，要安全的走到她的神器拖鞋那，然后干巴爹~
蟑螂的扩张模式如下:

在时间t如果单元（i，j）被蟑螂占据，则在时间t + 1个单元格（i + 1，j），（i-1，j），（i，j + 1），（i，j- 1）以及单元（i，j）将被蟑螂占据，如果相应的单元格是空的并且在迷宫的边界内。
如果蟑螂扩张另女孩不能成功走到拖鞋那，后果很严重。。

思路

以女孩所在位置BFS一次，找出到拖鞋的最少步数。
再以蟑螂的位置BFS一次，算出蟑螂扩张到拖鞋位置的最短时间。
要注意蟑螂扩张的模式，可能会使女孩在走向拖鞋的过程中无路可走。

输入输出分析

Input

2 //自己数吧~~~
5 5
S..#*
...#.
...##
.....
....X
5 5
S..#*
...#.
...#.
.....
....X

Output

yes
no

上代码

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <string.h>
using namespace std;
#define inf 1111111
int n, m;
char s[105][105];
int vis[105][105];
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

struct land{
    int x, y;
    int step;
};

int bfs(int xx, int yy)
{
    int i, r, c;
    land now; //在内部定义！！！！
    memset(vis, 0, sizeof(vis));
    queue <land> q;  //建立队列
    while(!q.empty()) //清空队列
        q.pop();
    now.x = xx;
    now.y = yy;
    now.step = 0;
    q.push(now); //入队
    vis[xx][yy] = 1;
    while(!q.empty()) //队列非空
    {
        land next;
        now = q.front();
        q.pop();
        if(s[now.x][now.y]=='X') return now.step; //到达，返回步数
        for(i = 0; i < 4; i++) //搜索
        {
            r = now.x + dx[i];
            c = now.y + dy[i];
            if(r>=0 && r<n && c>=0 && c<m && !vis[r][c] && (s[r][c]=='.'|| s[r][c]=='X')) //是否通行
            {
                vis[r][c] = 1;
                next.x = r;
                next.y = c;
                next.step = now.step + 1;
                q.push(next);
            }
        }
    }
    return inf;
}



int main (void)
{
    int t, i, j, sp1, sp2;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d %d", &n, &m);
        for(i = 0; i < n; i++)
            scanf("%s", s[i]);
        land st, h;
        sp1 = inf;
        sp2 = inf;
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < m; j++)
            {
                if(s[i][j] == '*')
                {
                    sp1 = min(sp1, bfs(i,j));
                }
                if(s[i][j] == 'S')
                {
                    sp2 = min(sp2, bfs(i,j));
                }
            }
        }
        if(sp2 < sp1) printf("yes\n");
        else printf("no\n");
    }
    return 0;
}