走出迷宫【牛客】

素颜马尾好姑娘i 2023-09-30 11:51 18阅读 0赞

输入描述:  
输入第一行一个整数T(1<=T<=10)  
接下来有T组测试数据，对于每一组测试数据，第一行输入2个数n和m(1<=n,m<=500)  
接下来n行，每行m个字符代表这个迷宫，每个字符都是上面4个中的一种  
数据保证只有一个起点和一个终点  
输出描述:  
对于每一组测试数据，如果可以的话输出YES，不可以的话输出NO  
示例1

输入
    1
    3 5
    s...x
    x...x
    ...tx
    
    输出
    YES

#include<iostream>
    #include <cstring>
    using namespace std;
    const int N = 510;
    int T;
    int n, m, t;
    char g[N][N];
    int d[N][N];
    void dfs(int sx, int sy){
        
    	if (g[sx][sy] == 't') t = 1;
    	
    	int dx[4] = {
        1, 0, -1, 0}, dy[4] = {
        0, 1, 0, -1};//坐标偏移量
    	
    	for (int i = 0; i < 4; i ++ ){
        
    		
            int x = sx + dx[i], y = sy + dy[i];//通过加上坐标偏移量实现坐标上下左右移动
            
            if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] != 'x' && !d[x][y]){
        
            	
                //前四个是判断当前位置是否出界，第五个是判断所在位置是否为通路，最后判断是否走过
                d[x][y] = 1;//标记当前位置走过了
                
                dfs(x, y);//dfs下一个位置
                
            }
        }
    }	
    
    
    int main(){
        
    	cin>>T;
    	while(T--){
        
    		  while(cin >> n >> m){
        
    	        int sx, sy;
    	        t = 0;//初始化
    	        memset(g, 0, sizeof g);//初始化
    	        memset(d, 0, sizeof d);//多初始化
    	
    	        for (int i = 0; i < n; i ++ )
    	            for (int j = 0; j < m; j ++ ){
        
    	                cin >> g[i][j];
    	                if (g[i][j] == 's') sx = i, sy = j;//标记起点的下标
    	            }
    	
    	        dfs(sx, sy);//从起点开始遍历
    	
    	        if (t) puts("YES");//输出加换行
    	        else puts("NO");//输出加换行
    	    }
    	}
    
        return 0;
    	
    	
    }