C++广度优先搜索：抓人游戏

Question

##广度优先搜索
抓人游戏
题目难度：中阶
时间限制：1000ms
内存限制：256MB
题目背景
预言家 大A 和 大B 在玩抓人游戏，大A每一个时间单位均移动一个单位，如果 大A 在某个单位时间与 大B 站在一起，那么 大A 就获胜，若T个时间单位后，大A 没获胜则 大B 获胜。但是 大A 是预言家，因此他能够预判 大B 的行动轨迹。

题目描述
大B 在一个边长为 N 的正方形迷宫内。大A 想让你帮他算算，他最短可以在几个单位时间后获胜。

大A 把这个房间的地图用符号画了出来，他规定:

. 代表这个地方是没有障碍的。

• 代表这个地方有障碍物，是不可走的。
  A 代表大A的初始位置。
  B 代表大B的初始位置。
  输入格式
  第一行 2 个整数，N 和 T ，空格隔开。

接下来的 N 行，每行 N 个字符，表示 大A 画的地图。

接下来的 T 行，每行 2 个整数x和y，表示 大B 在每个时间单位时的位置。

输出格式
第一行一个整数 K ，表示 大A 最短可以在过了 K 个单位时间后 获胜，如果他不可以在 大B 胜利前获胜，那么请输出 -1。

输入输出样例
输入 #1

5 3
.****
*..B.
A.***
*****
.....
2 3
2 2
3 2

输出 #1

2
说明/提示
样例解释#1：

大A 移动路径：3 1 -> 3 2 -> 2 2，

大B 移动路径：2 4 -> 2 3 -> 2 2，

因此最短时间为 2 。

提示：为了游戏的可玩性，所以他们规定 大A 走过的路不可再走。

对于所有数据 5 ≤ N ≤ 100 , 1 ≤ T ≤ 1000

Answer 1

#include <bits/stdc++.h>
using namespace std;

int vis[150][150],x,y,n,m,t,xx,yy,ti;
int bx[1050],by[1050];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
char ch;
struct node{
    int sx,sy,time;
};
queue<node> q;
int main(){
    cin >> n >> t;
    for (int i=1;i<=n;++i){
        for (int j=1;j<=n;j++){
            cin >> ch;
            if (ch=='.' || ch=='B'){
                vis[i][j]=0;
            }
            if (ch=='*'){
                vis[i][j]=1;
            }
            if (ch=='A'){
                vis[i][j]=1;
                q.push((node){i,j,0});
            }
        }
    }
    for (int i=1;i<=t;++i){
        cin >> bx[i] >> by[i];
    }
    while (!q.empty()){
        node u=q.front();
        q.pop();
        xx=u.sx,yy=u.sy,ti=u.time;
        for (int i=0;i<4;++i){
            int sx=xx+dx[i],sy=yy+dy[i];
            if (!vis[sx][sy] && sx && sy && sx<=n && sy<=n){
                if (sx==bx[ti+1] && by[ti+1]==sy && ti+1<=t){
                    cout << ti+1;
                    return 0;
                }else if (ti+1>t){
                    cout << -1 << endl;
                    return 0;
                }
                vis[sx][sy]=1;
                q.push((node){sx,sy,ti+1});
            }
        }
    }
    cout << -1 << endl;
    return 0;
}