竞赛讨论区 > 为什么这题不需要回溯?
头像
六娃lw
发布于 2021-01-16 17:47
+ 关注

为什么这题不需要回溯?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char c;
int N,M;
int bi,bj;
int dirs[4][2]{{1,0},{0,1},{-1,0},{0,-1}};
char mt[505][505];
bool visited[505][505];
bool dfs(int i,int j){
    if(mt[i][j]=='E'){return true;}
    visited[i][j]=true;
    for(int k=0;k<4;++k){
        int newI=i+dirs[k][0],newJ=j+dirs[k][1];
        if(newI>=0&&newI<N&&newJ>=0&&newJ<M&&!visited[newI][newJ]&&mt[newI][newJ]!='#'){
            if(dfs(newI,newJ))
                return true;
        }
    }
        // visited[i][j]=false; 为啥不要加这一句
    return false;
}
int main(){
    while(scanf("%d %d",&N,&M)!=EOF){
        memset(visited, false, sizeof(visited));
        for(int i=0;i<N;++i){
            for(int j=0;j<M;++j){
                scanf(" %c",&c);
                if(c=='S'){bi=i;bj=j;}
                mt[i][j]=c;
            }
        }
        if(dfs(bi,bj)){printf("Yes\n");}
        else{printf("No\n");}
    }
    return 0;
}

全部评论

(1) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐