dfs样例过不掉,有关注
查看原帖
dfs样例过不掉,有关注
1331383
CSP400pts楼主2025/1/13 21:41
#include<bits/stdc++.h>
using namespace std;
bool a[10][10],used[10][10];
int ans=2000000000;
void change(int i,int j) {
	a[i-1][j]=1-a[i-1][j];
	a[i+1][j]=1-a[i+1][j];
	a[i][j-1]=1-a[i][j-1];
	a[i][j+1]=1-a[i][j+1];
}
bool check() {
	bool flag=0;
	for(int i=1; i<=3; i++) {
		for(int j=1; j<=3; j++) {
			if(a[i][j]==0) {
				flag=1;
				return false;
			}
		}
	}
	return true;
}
void dfs(int step) {
	if(step>=10) return ;
	if(check()) ans=min(step,ans);
	for(int i=1; i<=3; i++) {
		for(int j=1; j<=3; j++) {
			if(!used[i][j]) {
				used[i][j]=1;
				change(i,j);
				dfs(step+1);
				change(i,j);
				used[i][j]=0;
			}
		}
	}
	return ;
}
int main() {
	for(int i=1; i<=3; i++) {
		for(int j=1; j<=3; j++) {
			cin>>a[i][j];
		}
	}
	dfs(0);
	cout<<ans<<endl;
	return 0;
}
2025/1/13 21:41
加载中...