填涂颜色
由数字00组成的方阵中，有一任意形状闭合圈，闭合圈由数字11构成，围圈时只走上下左右44个方向。现要求把闭合圈内的所有空间都填写成22.例如：6 \times 66×6的方阵（n=6n=6），涂色前和涂色后的方阵如下：
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1
输入格式
每组测试数据第一行一个整数n(1 \le n \le 30)n(1≤n≤30)
接下来nn行，由00和11组成的n \times nn×n的方阵。
方阵内只有一个闭合圈，圈内至少有一个00。
//感谢黄小U饮品指出本题数据和数据格式不一样. 已修改(输入格式)
输出格式
已经填好数字22的完整方阵。
输入格式：
6 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1
输出格式：
0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 2 2 1 1 1 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 1
分析：先在数组的最外层围一圈，然后从左上开始递归，横向和纵向搜索，不能斜着搜索，因为斜着的1也算作阻隔。把搜索过的数赋值为2，搜索时遇到1或2时回溯。除了1围成的0以外，其他的0没有被围起来有了外层圈就都应该都可以搜索到，于是外面的0就全部变成了2。在输出时把2还原为0就可以。而把0染色为2。
代码：
#include <bits/stdc++.h>
using namespace std;
int a[100][100];
void dg(int x, int y, int n){
if(x >= 0 && x <= n + 1 && y >= 0 && y <= n + 1){
if(a[x][y] == 1 || a[x][y] == 2) return ;
else{
a[x][y] = 2;
dg(x + 1, y, n);
dg(x - 1, y, n);
dg(x, y + 1, n);
dg(x, y - 1, n);
}
}
else return ;
}
int main(){
int n, i, j;
cin>>n;
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
cin>>a[i][j];
dg(0, 0, n);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++){
if(a[i][j] == 2) a[i][j] = 0;
else if(a[i][j] == 0) a[i][j] = 2;
}
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++) cout<<a[i][j]<<' ';
cout<<endl;
}
return 0;
}[USACO1.5]八皇后 Checker Challenge
题目描述
一个如下的 6 \times 66×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。
上面的布局可以用序列 2\ 4\ 6\ 1\ 3\ 52 4 6 1 3 5 来描述，第 ii 个数字表示在第 ii 行的相应位置有一个棋子，如下：
行号 1\ 2\ 3\ 4\ 5\ 61 2 3 4 5 6
列号 2\ 4\ 6\ 1\ 3\ 52 4 6 1 3 5
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 33 个解。最后一行是解的总个数。
输入格式
一行一个正整数 nn，表示棋盘是 n \times nn×n 大小的。
输出格式
前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。
输入样例：
6
输出样例：
2 4 6 1 3 5 3 6 2 5 1 4 4 1 5 2 6 3 4
分析：注意如何判断斜向是否没有数。其实只需要一个一维数组就能判断其所在的方向是否有数，假设数组啊[x][y]，右上到左下斜线上的数可以发现x+y为一个定值，而且与其平行的斜线上的点x+y的值都不一样，所以就可以用这个值判断这个斜线上是否已经有数。而左上到右下斜线可以发现y-x是一个定值，但是当y<x的时候就是负数了，所以统一加一个行数n，也就是y-x+n，它也是一个定值，也可以代表斜线。从第一行开始从左往右搜索，遇到符合条件的点就记录数字，并且将这个位置标记，所在斜线也标记，然后跳到下一行继续从左往右搜索点。如果搜索的行数超过了n，那说明已经找到了n个符合要求的点，将其输出并且回溯继续搜索。
代码：
#include<bits/stdc++.h>
using namespace std;
int n,ans=0;
int a[200],b[200],c[200],d[200];
void dfs(int k)
{
if(k>n)
{
if(ans<3)
{
for(int i=1;i<=n;i++)
cout<<d[i]<<" ";
cout<<endl;
}
ans++;
return ;
}
for(int i=1;i<=n;i++)
{
if(a[i]==0&&b[i+k]==0&&c[i-k+n]==0)
{
d[k]=i;
a[i]=1;b[k+i]=1;c[i-k+n]=1;
dfs(k+1);
a[i]=0;b[k+i]=0;c[i-k+n]=0;
}
}
}
int main ()
{
cin>>n;
dfs(1);
cout<<ans<<endl;
return 0;
}