80分dfs求调!
  • 板块B3625 迷宫寻路
  • 楼主Syncc
  • 当前回复4
  • 已保存回复4
  • 发布时间2023/8/10 15:05
  • 上次更新2023/11/3 04:43:31
查看原帖
80分dfs求调!
766788
Syncc楼主2023/8/10 15:05
#include<bits/stdc++.h>
using namespace std;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0},n,m;
bool vis[1005][1005],flag=0;
char g[1005][1005];
void dfs(int x,int y){
	if(x==n && y==m){
		flag=1;
        return ;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<1 || nx>n || ny<1 || ny>m){
			continue;
		}
		if(g[nx][ny]=='.' && vis[nx][ny]==0){
			vis[nx][ny]=1;
			dfs(nx,ny);
		}
	}
}
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>g[i][j];
		}
	}
	if(g[1][1]=='#' || g[n][m]=='#'){
		cout<<"No";
		return 0;
	} 
	vis[1][1]=1;
	dfs(1,1);
	if(flag==0){
		cout<<"No";
	}else{
		cout<<"Yes";
	}
	return 0;
}
2023/8/10 15:05
加载中...