5分求调
查看原帖
5分求调
1298242
wangzhongqian楼主2024/3/20 20:50
#include <bits/stdc++.h>
using namespace std;
int d[4][2]={{0,1},{1,0},{0,-1},{-1,0}},cnt,n,m,tot,res;
char t[10][10],s[10][10];
bool vis[10][10];
bool dfs2(int x, int y, int prex, int prey){
	if(vis[x][y]) return 0;
	--cnt, vis[x][y]=1;
	for(auto [tx, ty]:d){
		tx+=x, ty+=y;
		if((tx==prex && ty==prey)|| tx<1 || ty<1 || tx>n || ty>m || t[tx][ty]!='+') continue;
		if(!dfs2(tx, ty, x, y)) return 0;
	}
	return 1;
}

void dfs(int x, int y, int tot){
	if(y==m+1) ++x, y=1;
	if(0.8*((n-x)*m+m-y+1)+tot<=res) return;
	memset(vis, 0, sizeof vis);
	if(x==n+1){
		cnt=tot;
		if(tot>res && dfs2(x, y, -1, -1) && !cnt){
			memcpy(ans,t,sizeof(t));
			res=tot;
		}
		return;
	}
	if(s[x][y]!='#'){
		t[x][y]='+';
		if(dfs2(x, y, -1, -1)) //2
			dfs(x, y+1, tot+1);
		t[x][y]=s[x][y];
	}
	if(s[x][y]!='+') dfs(x, y+1, tot);
}
int main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> s[i][j];
			t[i][j]=s[i][j];
		}
	}
	dfs(1,1,1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cout << t[i][j];
		cout << endl;
	}
	return 0;
}
2024/3/20 20:50
加载中...