走出迷宫

走出迷宫

题目分析:

DFS入门题，走迷宫

代码如下:

#include<bits/stdc++.h>

using namespace std;

#define  mm(a,x) memset(a,x,sizeof a)
#define  mk make_pair
#define ll long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f
#define lowbit(x) (x) & (-x)
#define eps 1e-6

const int N = 510;

int n,m;
char g[N][N];
bool st[N][N];
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};
int xa,ya,xb,yb;

bool dfs(int x,int y){
    if(x == xb && y == yb){
        return true;
    }
    st[x][y] = true;
    for(int i = 0; i < 4; i ++ ){
        int a = x + dx[i];
        int b = y + dy[i];
        if(a < 1 || a > n || b < 1 || b > m) continue;
        if(st[a][b] || g[a][b] == '#') continue;
        st[a][b] = true;
        if(dfs(a,b)) return true;
    }
    return false;
} 
int main() {
    while(cin >> n >> m){
        mm(g,0);mm(st,0);
        for(int i = 1; i <= n; i ++ ){
            for(int j = 1; j <= m; j ++ ){
                cin >> g[i][j];
                if(g[i][j] == 'S') xa = i,ya = j;
                if(g[i][j] == 'E') xb = i,yb = j;
            }
        }
        if(dfs(xa,ya)) cout<<"Yes\n";
        else cout<<"No\n";
    }    
    return 0;
}