填涂颜色

由数字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;
}