蓝桥杯 01游戏

问题描述

小蓝最近玩上了 01 游戏，这是一款带有二进制思想的棋子游戏。

游戏在一个大小为 N × N 的棋盘上进行。棋盘上的每个位置都需要放置一个数字 0 或 1。初始情况下，棋盘上有一部分位置已经放置了固定的数字，玩家不可以更改这些位置。其他的空白位置由玩家填入数字。

玩家需要使得最终棋盘满足以下条件：

1. 所有的空白位置都必须填入 0 或 1；
2. 在水平方向或垂直方向上，相同的数字不能连续出现超过两次；
3. 每一行和每一列上，数字 0 和 1 的数量必须相等（例如当 N = 4 时，每行/列需要有 2 个 0 和 2 个 1）；
4. 每一行必须是唯一的，不能和其他行完全相同；同理，每一列也必须是唯一的。

题目保证所有测试数据都有且仅有一个唯一的解。

---

输入格式

• 第一行包含一个整数 N，表示棋盘的大小。
• 接下来的 N 行每行包含 N 个字符，字符只可能是 0、1 或 _：
  • 0 表示该位置固定为数字 0；
  • 1 表示该位置固定为数字 1；
  • _ 表示该位置为空白，由玩家填入。

---

输出格式

输出 N 行，每行 N 个字符，只包含 0 或 1，表示填完后的棋盘。

---

样例输入

6
_0____
____01
__1__1
__1_0_
______
__1___

---

样例输出

100110
010101
001011
101100
110010
011001

---

评测用例规模与约定

• 对于 60% 的评测用例，2 ≤ N ≤ 6
• 对于 100% 的评测用例，2 ≤ N ≤ 10，且 N 为偶数

---

运行限制

编程语言	最大运行时间	最大运行内存
C++	1 秒	256 MB
C	1 秒	256 MB
Java	2 秒	256 MB
Python3	3 秒	256 MB
PyPy3	3 秒	256 MB
Go	3 秒	256 MB
JS	3 秒	256 MB

---

难度：困难
标签：2023、国赛、搜索、剪枝

c++代码

#include<bits/stdc++.h>using namespace std;int N;
vector<vector<int>> arr;
string s;
bool sym = false;
vector<int> col0, row0, col1, row1;bool check(int i, int j) {if (i >= 2) {if (arr[i][j] == 0 && arr[i - 1][j] == 0 && arr[i - 2][j] == 0) return false;if (arr[i][j] == 1 && arr[i - 1][j] == 1 && arr[i - 2][j] == 1) return false;}if (j >= 2) {if (arr[i][j] == 0 && arr[i][j - 1] == 0 && arr[i][j - 2] == 0) return false;if (arr[i][j] == 1 && arr[i][j - 1] == 1 && arr[i][j - 2] == 1) return false;}return true;
}bool myunique() {unordered_set<string> st;for (int i = 0; i < N; i++) {string str;for (int j = 0; j < N; j++) {str += to_string(arr[i][j]);}if (st.find(str) != st.end()) return false;else st.insert(str);}st.clear();for (int i = 0; i < N; i++) {string str;for (int j = 0; j < N; j++) {str += to_string(arr[j][i]);}if (st.find(str) != st.end()) return false;else st.insert(str);}return true;
}void dfs(int i, int j, int cur) {if (sym || (arr[i][j] != -1 && arr[i][j] != cur)) return;int x = i, y = j;bool key = arr[i][j] == -1 ? true:false;arr[i][j] = cur;if (!check(i, j)) {if (key) arr[i][j] = -1;return;}if (arr[i][j] == 0) row0[i]--, col0[j]--;else row1[i]--, col1[j]--;if (j == N - 1) x++, y = 0;else y++;if (x == N) {if (myunique()) {sym = true;for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {printf("%d", arr[i][j]);}printf("\n");}}return;}if (row0[x] > 0 && col0[y] > 0) dfs(x, y, 0);if (row1[x] > 0 && col1[y] > 0) dfs(x, y, 1);if (arr[i][j] == 0) row0[i]++, col0[j]++;else row1[i]++, col1[j]++;if (key) arr[i][j] = -1;
}int main() {cin >> N;arr = vector<vector<int>>(N, vector<int>(N));row0 = vector<int>(N, N / 2), col0 = vector<int>(N, N / 2);row1 = vector<int>(N, N / 2), col1 = vector<int>(N, N / 2);for (int i = 0; i < N; i++) {cin >> s;for (int j = 0; j < N; j++) {if (s[j] == '0') arr[i][j] = 0;else if (s[j] == '1') arr[i][j] = 1;else arr[i][j] = -1;}}dfs(0, 0, 0);dfs(0, 0, 1);return 0;
}//by wqs