60分dfs求调
查看原帖
60分dfs求调
284752
gzcsdjj楼主2023/7/28 18:01
#include<bits/stdc++.h>
using namespace std;
int t=clock();
int n,m;
char a[101][101];
bool vis[101][101],ans=false;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

void dfs(int x,int y) {
	if(x==n&&y==m) {
		ans=true;
//		cnt=min(cnt,num);
		return;
	}
	
	for(int i=0; i<4; i++) {
		int tx=dx[i]+x;
		int ty=dy[i]+y;
		if(a[tx][ty]=='#')continue;
		if(tx<1||ty<1||tx>n||ty>m)continue;
		if(vis[tx][ty]==1)continue;
		vis[tx][ty]=1;
//		num++;
		dfs(tx,ty);
		vis[tx][ty]=0;
		if(ans)return;
//		num--;
	}
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>a[i][j];
		}
	}
	//vis[1][1]=1;
	dfs(1,1);
	if(ans)printf("Yes");
	else printf("No");
//	cout<<endl<<"t="<<clock()-t;
	return 0;
}
2023/7/28 18:01
加载中...