为什么我暴力算出4*4的方格中有18种合法方案?
查看原帖
为什么我暴力算出4*4的方格中有18种合法方案?
463956
incra楼主2023/1/8 16:40

暴力代码:

#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;
int n = 4;
int g[10][10];
int cnt = 0;
unordered_set <string> se;
bool check () {
	for (int i = 1;i <= n;i++) {
		for (int j = 1;j <= n;j++) {
			if (i + 2 <= n && g[i][j] == g[i + 1][j] && g[i + 1][j] == g[i + 2][j]) return false;
			if (j + 2 <= n && g[i][j] == g[i][j + 1] && g[i][j + 1] == g[i][j + 2]) return false;
			if (i + 2 <= n && j + 2 <= n && g[i][j] == g[i + 1][j + 1] && g[i + 1][j + 1] == g[i + 2][j + 2]) return false;
			if (i + 2 <= n && j >= 2 && g[i][j] == g[i + 1][j - 1] && g[i + 1][j - 1] == g[i + 2][j - 2]) return false;
		}
	}
	return true;
}
void dfs (int u,string s) {
	if (u > 16) {
		for (int i = 0;i < s.size ();i++) {
			g[i / 4 + 1][i % 4 + 1] = s[i] - '0';
		}
		if (check ())  {
			se.insert (s);
			for (int i = 1;i <= 4;i++) {
				for (int j = 1;j <= 4;j++) cout << g[i][j];
				cout << endl;
			}
			cout << endl;
		}
		return ;
	}
	dfs (u + 1,s + '0');
	dfs (u + 1,s + '1');
}
int main () {
	memset (g,-1,sizeof (g));
	dfs (1,"");
	cout << se.size () << endl;
	return 0;
}

输出:

0011

1100

0011

1010


0011

1100

0011

1100


0101

0100

1011

1010


0101

0101

1010

1010


0101

1010

1010

0101


0101

1100

0011

1010


0101

1100

0011

1100


0101

1101

0010

1010


0110

1001

0110

1001


1001

0110

1001

0110


1010

0010

1101

0101


1010

0011

1100

0011


1010

0011

1100

0101


1010

0101

0101

1010


1010

1010

0101

0101


1010

1011

0100

0101


1100

0011

1100

0011


1100

0011

1100

0101


18

2023/1/8 16:40
加载中...