dfs哪里有问题?本机调用21669层后崩栈。
查看原帖
dfs哪里有问题?本机调用21669层后崩栈。
738761
HappyDavid楼主2023/10/2 18:10
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
lint m[4][4], ans;
void dfs(lint depth) {
	bool ok = true;
	for (lint i = 1; i <= 3 && ok; i++) {
		for (lint j = 1; j <= 3 && ok; j++) {
			if (m[i][j] == 0) {
				ok = false;
			}
		}
	}
	if (ok) {
		ans = min (ans, depth - 1);
	} else {
		for (lint i = 1; i <= 3; i++) {
			for (lint j = 1; j <= 3; j++) {
				m[i][j] = m[i][j] xor 1;
				m[i - 1][j] = m[i - 1][j] xor 1;
				m[i][j - 1] = m[i][j - 1] xor 1;
				m[i + 1][j] = m[i + 1][j] xor 1;
				m[i][j + 1] = m[i][j + 1] xor 1;
				dfs (depth + 1);
				m[i][j] = m[i][j] xor 1;
				m[i - 1][j] = m[i - 1][j] xor 1;
				m[i][j - 1] = m[i][j - 1] xor 1;
				m[i + 1][j] = m[i + 1][j] xor 1;
				m[i][j + 1] = m[i][j + 1] xor 1;
			}
		}
	}
}
int main() {
	scanf ("%lld%lld%lld%lld%lld%lld%lld%lld%lld", &m[1][1], &m[1][2], &m[1][3], &m[2][1], &m[2][2], &m[2][3], &m[3][1], &m[3][2], &m[3][3]);
	ans = 2147483648;
	dfs (1);
	printf ("%lld\n", ans);
	return 0;
}
2023/10/2 18:10
加载中...