博客

#include <bits/stdc++.h>
using namespace std;
const int maxn = 11;
int n, m, t, maxd, kase;
bool G[maxn][maxn], vis[4][maxn * 2];
bool guard()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			if (G[i][j] && ! vis[0][i] && !vis[1][j] && !vis[2][i + j] && !vis[3][i - j + maxn])
				return false;
}
bool dfs(int i, int j, int d)
{
	if (d == maxd)
		if (guard()) return true;
		else return false;
	for (; i < n; i++, j %= m)
		for (; j < m; j++)
		{
			bool tmp1 = vis[0][i], tmp2 = vis[1][j], tmp3 = vis[2][i + j], tmp4 = vis[3][i - j + maxn];
			vis[0][i] = vis[1][j] = vis[2][j + i] = vis[3][i - j + maxn] = 1;
			if (dfs(i, j + 1, d + 1)) return true;
			vis[0][i] = tmp1, vis[1][j] = tmp2, vis[2][i + j] = tmp3, vis[3][i - j + maxn] = tmp4;
		}
	return false;
}
int main(int argc, char const *argv[])
{
	while (cin >> n  && n)
	{
		cin >> m; cin.get();
		for (int i = 0; i < n; cin.get(), i++)
			for (int j = 0; j < m; j++)
				G[i][j] = (cin.get() == 'X' ? 1 : 0);
		for (maxd = 0; maxd < 5; ++maxd)
		{
			memset(vis, 0, sizeof(vis));
			if (dfs(0, 0, 0)) break;
		}
		cout << "Case " << ++kase << ": " << maxd << endl;
	}
	return 0;
}

最多5个皇后