myj的尘歌壶

Time Limit: 1000 MS Memory Limit: 262144 K Total Submit: 380(54 users) Total Accepted: 76(42 users) Rating:  Special Judge: No

Description

最近myj沉迷原神无法自拔，在原神的游戏系统中，有一个叫做尘歌壶的家园系统，你可以在里面放置各种物品 但是myj是一个急功近利的人，为了白嫖到奖励，不惜一切代价，而这一行为导致他的尘歌壶里面一片混乱 某一天，他在正常游戏的时候，发现自己在尘歌壶里面迷路了，而他发现他的尘歌壶可以转化为一个n*m的简单二维图，其中1表示障碍物，0表示空地。若你位于一格0上，那么你可以移动到相邻4格中的任意一格0上 现在myj给你他所在的位置，和他想去的位置，你能帮他找找是否存在一条路径使他在混乱的尘歌壶中走到目标位置吗？

Input

第一行一个数字T，表示有T组测试数据 对于每一组数据： 第一行包含两个整数n，m，表示myj给你的地图大小有n行m列 接下来有n行由01构成的字符串，每行字符串有m个字符，若当前字符为1，表示不可以通过。0表示可以正常通过 最后一行包含四个整数sx，sy，ex，ey，分别表示myj现在所在的点坐标，和终点的点坐标 n,m≤500，T≤10，数据保证起点和终点不是障碍物，且对于所有数据而言，n*m的总和不大于1e7

Output

如果myj能够顺利到达，输出YE5 否者输出N0

Sample Input

1  3 3 001 100 110 1 1 3 3

Sample Output

YE5

Hint

输出建议直接复制题目 每输出一行都应该有一个换行符 行末没有多余空格 迷宫左上角坐标为（1，1），右下角为（n，m） 提示：可以参考马老师讲过的走迷宫代码，注意复杂度！

Source

20211016

Author

马英杰

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
 
constexpr int N=505;
char s[N][N];
int z,n,m,sx,sy,ex,ey;
bool vis[N][N];
int dx[4]={0,1,-1,0},dy[4]={1,0,0,-1};
 
void bfs(int x,int y){
    queue<pair<int,int>>q;
    q.push(make_pair(x,y));
    while(!q.empty()){
        auto t=q.front();
        q.pop();
        if(t.first==ex&&t.second==ey){
            printf("YE5\n");
            return;
        }
        for(int i=0;i<4;i++){
            int xx=t.first+dx[i],yy=t.second+dy[i];
            if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&vis[xx][yy]==0&&s[xx][yy]=='0'){
                vis[xx][yy]= true;
                q.push(make_pair(xx,yy));
            }
        }
    }
    printf("N0\n");
    return;
}
int main() {
    scanf("%d", &z);
    while (z--) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
               cin>>s[i][j];
            }
        }
        scanf("%d%d%d%d", &sx, &sy, &ex, &ey);
        s[sx][sy]= true;
        bfs(sx, sy);
        memset(s,0,sizeof(s));
        memset(vis, false,sizeof(vis));
    }
}