描述:
输出8皇后问题所有结果。
输入:
没有输入。
输出:
每个结果第一行是No n:的形式,n表示输出的是第几个结果;下面8行,每行8个字符,‘A’表示皇后,‘.’表示空格。不同的结果中,先输出第一个皇后位置靠前的结果;第一个皇后位置相同,先输出第二个皇后位置靠前的结果;依次类推。
输出样例:
输出的前几行:
No 1:
A.......
....A...
.......A
.....A..
..A.....
......A.
.A......
...A....
No 2:
A.......
.....A..
.......A
..A.....
......A.
...A....
.A......
....A...
题解:
#include <iostream>
#include <cstring>
using namespace std;
const int N = 8;
char a[N][N];
int b[N][N];
int num = 0;
void init();
void dfs(int t);
void prog(int x, int y, int z);
void output();
int main()
{
init();
dfs(0);
}
void init()
{
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
a[i][j] = '.';
}
}
memset(b, 0, sizeof(b));
}
void dfs(int t)
{
if (t == N)
{
output();
return;
}
for (int i = 0; i < N; i++)
{
if (b[t][i] == 0)
{
a[t][i] = 'A';
prog(t, i, 1);
dfs(t+1);
a[t][i] = '.';
prog(t, i, -1);
}
}
}
void prog(int x, int y, int z)
{
for (int i = 0; i < N; i++)
{
b[x][i] += z;
b[i][y] += z;
if (x+i < N && y+i < N)
{
b[x+i][y+i] += z;
}
if (x-i >= 0 && y+i < N)
{
b[x-i][y+i] += z;
}
}
for (int j = 1; j < N; j++)
{
if (x-j >= 0 && y-j >= 0)
{
b[x-j][y-j] += z;
}
if (x+j < N && y-j >= 0)
{
b[x+j][y-j] += z;
}
}
}
void output()
{
num++;
cout << "No " << num << ":" << endl;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << a[i][j];
}
cout << endl;
}
}