B3625题解

syhx · 2025-10-24 13:41:30 · 学习·文化课

小声BB：上次写题解是啥时候了。。。

啊！dfs！
思路很简单，毕竟是 B 字头。
直接上代码吧。

#include<iostream>
#include<vector>
using namespace std;
vector<int> q[105];
//不要在意vector，这是我拿模版改的。
int m,n; 
bool flag=0;
//用于判断最后能不能到达终点
bool can_visit[105][105];
//这个点能不能到
bool is_visit[105][105];
//这个点有没有到过
int dx[]={0,1,-1,0,0};
int dy[]={0,0,0,1,-1};
//方向数组
void dfs(int nowx,int nowy){
    if (nowx==n&&nowy==m) flag=1;
  //如果已经是终点了就把 flag 设为 1
  //我代码当时没有写退出循环
  //所以如果没有这个，下一次循环的结果会覆盖掉这一次
    for(int i=1;i<=4;i++){
        int tx=nowx+dx[i];
        int ty=nowy+dy[i];
    //移动
        if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&is_visit[tx][ty]==0&&can_visit[tx][ty]==1){
      //别看这么长一串，思路很简单。
      //依次判断：左右上下有没有出界，这个点有没有去过，这个点能不能到
      //笑死，写错四次
            is_visit[tx][ty]=1;
      //该点标记为已来过
            dfs(tx,ty);
      //递推下一个点
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
  //优化
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char a; cin>>a;
            if(a=='.') can_visit[i][j]=1;
        //简单的存图
        }
    }
    dfs(1,1);
  //从起点开始搜索
    if(flag==1) cout<<"Yes";
    else cout<<"No";
    return 0;
}

尽管这个函数有一点小问题导致它要把整张图扫完再退出，但对于 n,m<100 来说还是够了。

@syhx