【01游戏——DFS】

题目

代码

#include <bits/stdc++.h>
using namespace std;const int N = 11;int n;
char g[N][N];
char ng[N][N];
bool Find = false;bool check(int x, int y) //只用查最新的坐标相关的数据
{//连续长度不能超过2if(x - 2 >= 1 && ng[x][y] == ng[x-1][y] && ng[x-1][y] == ng[x-2][y]) return false;if(y - 2 >= 1 && ng[x][y] == ng[x][y-1] && ng[x][y-1] == ng[x][y-2]) return false;//数量各一半 && 不能相同if(x == n){int cnt = 0;for(int i = n; i; i--)if(ng[i][y] == '1')cnt++;if(cnt != n / 2) return false;for(int j = y-1; j; j--){int k = 1;for(; k <= n; k++)if(ng[k][j] != ng[k][y]) break;if(k > n) return false;}}if(y == n){int cnt = 0;for(int j = n; j; j--)if(ng[x][j] == '1')cnt++;if(cnt != n / 2) return false;for(int i = x-1; i; i--){int k = 1;for(; k <= n; k++)if(ng[i][k] != ng[x][k]) break;if(k > n) return false;}}return true;
}
void print()
{for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)cout << ng[i][j];cout << '\n';}
}
void dfs(int x, int y)
{if(Find) return; //找到唯一解，结束if(y > n) {x++, y = 1;} //合法化坐标if(x > n) //结束搜索，立马输出{Find = true;print();return;}if(g[x][y] == '_'){ng[x][y] = '0';if(check(x, y))dfs(x, y+1);ng[x][y] = '1';if(check(x, y))dfs(x, y+1);}else{ng[x][y] = g[x][y];if(check(x, y))dfs(x, y+1);}
}
int main()
{ios::sync_with_stdio(0); cin.tie(0);cin >> n;for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)cin >> g[i][j];dfs(1, 1);
}