AT_abc308_d [ABC308D] Snuke Maze 题解

Ray2009_ · 2024-11-05 22:35:03 · 题解

大家好，我是 Ray2009_，这是我这个蒟蒻的第一篇 gosh 题解。

前言：

这道题不知为何只有 BFS 的算法题解，于是热爱暴力（菜）的我用一篇 DFS 题解把思路理顺，复习一下（当然不是为了钻空子刷估值）~。

思路：

首先我们定义字符串 p 为整条正确线路上的所有字符，然后设整个图的第一个点为 s，用DFS暴力枚举一遍所有点，如该点为正确线路上的点就标记该点。跑到最右下角就退出。

代码如下（坑点和细节在下面有标注）：

AC记录

https://www.luogu.com.cn/record/187037667

#include<bits/stdc++.h>//万能头
using namespace std;
int n,m;
char s[508][508];
bool b[508][508];//标记用
bool f=0;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
string p="snuke";
inline int read(){//快读，其实可以不加
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
bool ck(int x,int y){//检查越界，写在下面可能会有点乱
    if(x<1||x>n||y<1||y>m) return 0;
    return 1;
}
void dfs(int x,int y,int c){
    if(x==n&&y==m){//到边界就退出
        f=1;
        return;
    } 
    for(int i=0;i<4;i++){
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(ck(nx,ny)&&!b[nx][ny]&&s[nx][ny]==p[(c+1)%5]){//判断是否是正确线路上的点
            b[nx][ny]=1;//是的话就标记
            dfs(nx,ny,c+1);
            //注：这里不需要 b[nx][ny] = 0;，因为一个点没必要搜多次，写的话会TLE。
        }
    }
}
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++)for(int j=1;j<=m;j++) cin>>s[i][j];//输入
    if(s[1][1]=='s') dfs(1,1,0);//初始设s
    if(f) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}