BFS和DFS入门题 洛谷B3625

题目链接：

题目描述：

解题思路：

用一个数组记录能到的点，用DFS或者用BFS从起点开始遍历，将所有的能到的点对应的数组置为1，写代码的时候注意边界处理。

BFS代码

首先将起点入队列，然后通过起点扩展其他节点，标记所有能到的节点。最后通过vis[n][m]就能得出答案了。用BFS还可以求最短路径，最小消费。因为BFS第一次到达的一定是最短的。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char arr[105][105];
int vis[105][105];
int fx[4][2]={
          
   {
          
   1,0},{
          
   -1,0},{
          
   0,1},{
          
   0,-1}};//定义上下左右四个方向
struct node{
          
   
    int x,y;
};
queue<node>q;
int main(){
          
   
  	cin>>n>>m;
  	for(int i=1;i<=n;i++){
          
   
  		for(int j=1;j<=m;j++){
          
   
  			cin>>arr[i][j];
		}
	}
	q.push({
          
   1,1});//将起点加入队列
	vis[1][1]=1;//标记起点已经访问过，防止往回走
	while(q.size()){
          
   
        node p;
        p=q.front();//取队头
        q.pop();//弹出队头
        for(int i=0;i<4;i++){
          
   
            int x,y;
            x=p.x+fx[i][0];
            y=p.y+fx[i][1];
            if(x>0&&x<=n&&y>0&&y<=m&&vis[x][y]==0&&arr[x][y]!=#){
          
   
                q.push({
          
   x,y});//符合条件的入队列
                vis[x][y]=1;//标记访问过
            }
        }
	}
	if(vis[n][m]){
          
   
        cout<<"Yes" ;
	}else{
          
   
        cout<<"No";
	}
	return 0;
}

DFS代码

思路同BFS差不多，拿起点去扩展，直到把所有能到的节点遍历完。

#include<bits/stdc++.h>
using namespace std;
int n,m;
char arr[105][105];
int vis[105][105];
int fx[4][2]={
          
   {
          
   1,0},{
          
   -1,0},{
          
   0,1},{
          
   0,-1}};
void dfs(int x,int y){
          
   
    vis[x][y]=1;
    for(int i=0;i<4;i++){
          
   
        int x1,y1;
        x1=x+fx[i][0];
        y1=y+fx[i][1];
        if(x1>0&&x1<=n&&y1>0&&y1<=m&&vis[x1][y1]==0&&arr[x1][y1]!=#)
            dfs(x1,y1);
    }
}
int main(){
          
   
  	cin>>n>>m;
  	for(int i=1;i<=n;i++){
          
   
  		for(int j=1;j<=m;j++){
          
   
  			cin>>arr[i][j];
		}
	}
	dfs(1,1);
	if(vis[n][m]){
          
   
        cout<<"Yes" ;
	}else{
          
   
        cout<<"No";
	}
	return 0;
}