40pts dfs求助
查看原帖
40pts dfs求助
939596
Use_Imagination楼主2023/7/26 21:23
#include<bits/stdc++.h>
using namespace std;
int n,m,a[114][514],dx[4]={-1,0,1,0},dy[4]={0,-1,0,1},vis[10001][10001];
char ch;
bool found;
void dfs(int x,int y){
	if(x==n&&y==m){
		found=1;
		return;
	}
	vis[x][y]=1;
	for(int i=0;i<4;i++){
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(!(tx>=1&&tx<n&&ty>=1&&ty<m&&vis[tx][ty]==0&&a[tx][ty]!='#'))
			continue;
		if(a[tx][ty]==0)
			dfs(tx,ty);
	}
} 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch;
			if(ch=='#')	a[i][j]=1;
		}
	}
	if(a[1][1]==1||a[n][m]==1){
		cout<<"No";
		return 0;
	}
	dfs(1,1);
	if(found) cout<<"Yes";
	else cout<<"No";
	return 0;
}
2023/7/26 21:23
加载中...