蒟蒻求问,我的DFS有什么问题?
查看原帖
蒟蒻求问,我的DFS有什么问题?
222104
_yjh楼主2020/5/13 18:19
#include<iostream>
#define MAXN 1001
using namespace std;
int n,m,ans=1e9,sum,mp[1005][1005];
bool vis[1005][1005];
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
const int col[]={0,1}; 
void dfs(int x,int y,bool magic) {
	if(sum>=ans) {
		return ;
	}
	if(x==n&&y==n) {
		ans=min(ans,sum);
		return ;
	}
	for(int i=0;i<=3;i++) {
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(tx<=0||tx>n||ty<=0||ty>n||vis[tx][ty]==true) continue;
		vis[tx][ty]=true;
		if(mp[x][y]==mp[tx][ty]) {
			dfs(tx,ty,false);
		}
		else {
			if(mp[tx][ty]!=-1) { //-1即无色 
				sum++;
				dfs(tx,ty,false);
				sum--;
			}
			else {
				if(magic==true) continue;
				for(int i=0;i<=1;i++) {
					mp[tx][ty]=col[i];
					sum+=2;
					dfs(tx,ty,true);
					mp[tx][ty]=-1;
					sum-=2;
				}
			}
		}
		vis[tx][ty]=false;
	}
}
int main() {
	vis[1][1]=true;
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=n;j++) {
			mp[i][j]=-1;
		}
	}
	for(int i=1;i<=m;i++) {
		int x,y,color;
		cin>>x>>y>>color;
		mp[x][y]=color;
	}
	dfs(1,1,false);
    if(ans==1e9) {
    	cout<<-1<<'\n';
	}
	else cout<<ans<<'\n';
	return 0;
} 
2020/5/13 18:19
加载中...