不知到底哪里有问题
查看原帖
不知到底哪里有问题
1133455
miao2013楼主2024/5/28 20:06

不知到底哪里有问题

#include<bits/stdc++.h>
using namespace std;
char c[1100][1100];
int vis[1100][1100];
char daan[1100][1100];
int diri[5]={0,1,-1,0,0};
int dirj[5]={0,0,0,1,-1};
int n,m,k,ans=1,Min=(1024*1024+1),sum=0;
void dfs(int i,int j,int cnt,int f){
	if(vis[i][j]){
		return;
	}
	if(cnt==n*m-sum){
		if(f<Min){
			ans=0;
			Min=f;
			for(int i=1;i<=n;i++){
				for(int j=0;j<m;j++){
					daan[i][j]=c[i][j];
				}
			}
		}
		return;
	}
	vis[i][j]=1;
	int s=0,x,y;
	for(int d=1;d<=4;d++){
		int ni=i+diri[d];
		int nj=j+dirj[d]; 
		if(ni<1||nj<0||ni>n||nj>=m||c[ni][nj]=='#'){
			s++;
		}
		else{
			x=ni;
			y=nj;
		}
	}
	if(s==3){
		vis[x][y]=0;
		dfs(x,y,cnt,f);
	}
	for(int d=1;d<=4;d++){
		int ni=i+diri[d];
		int nj=j+dirj[d]; 
		if(ni>=1&&nj>=0&&ni<=n&&nj<m&&c[ni][nj]=='.'){
			dfs(ni,nj,cnt+1,f);
			c[ni][nj]='X';
			sum++;
			vis[i][j]=0;
			dfs(i,j,cnt+1,f+1);
			c[ni][nj]='.';
			sum--;	
		}
	}
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=0;j<m;j++){
			c[i][j]=s[j];
			if(c[i][j]=='#'){
				sum++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<m;j++){
			int cnt=0;
			for(int d=1;d<=4;d++){
				int ni=i+diri[d];
				int nj=j+dirj[d]; 
				if(ni<1||nj<0||ni>n||nj>=m||c[ni][nj]=='#'){
					cnt++;
				}
			}
			if(cnt==4){
				c[i][j]='X';
				sum++;
			}
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<m;j++){
			if(c[i][j]=='.'){
				dfs(i,j,1,0);
			}
		}
	}
	if(ans==1){
		for(int i=1;i<=n;i++){
			for(int j=0;j<m;j++){
				cout<<c[i][j];
			}
			cout<<endl;
		}
		return 0;
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<m;j++){
			cout<<daan[i][j];
		}
		cout<<endl;
	}
}

P3836 请各位大佬帮忙看一下

2024/5/28 20:06
加载中...