状压dp WA 63
查看原帖
状压dp WA 63
972576
LiDongchen666楼主2024/5/25 15:06
/*
限制:
思路:
时间复杂度:
*/
#include<bits/stdc++.h>
#define f1 for(int i = 1; i <= n; i++)
#define f2 for(int j = 1; j <= m; j++)
#define int long long
using namespace std;
const int N = 19;
bool a[N][N], ans[N][N], t[N][N];
int dir[4][2] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};
int n, m;
void init(){
	f1 f2 t[i][j] = a[i][j];
}
void print(){
	f1{
		f2 printf("%lld ", ans[i][j]);
		puts("");
	}
}
void exchange(int bit){
	for(int i = n; i >= 1; i--){
		for(int j = m; j >= 1; j--){
			ans[i][j] = bit & 1;
			bit >>= 1;
		}
	}
}
bool check(){
	f1 f2
		if(ans[i][j]){
			t[i][j] = !t[i][j];
			for(int k = 0; k < 4; k++)
				t[i + dir[k][0]][j + dir[k][1]] = !t[i + dir[k][0]][j + dir[k][1]];
		}
	f1 f2 if(t[i][j]) return 0;
	return 1;
}
signed main(){
	scanf("%lld%lld", &n, &m);
	f1 f2 scanf("%lld", &a[i][j]);
	int tle = 0;
	for(int step = 0; step <= (1 << n * m) - 1; step++){
		exchange(step);
		init();
		if(check()){
			print();
			return 0;
		}
		tle += n * m * 6;
		if(tle >= 1e8){
			break;
		}
	}
	printf("IMPOSSIBLE");
	return 0;
}

字典序没问题吧

2024/5/25 15:06
加载中...