73 N皇后问题 (20 分)

卡在题目里的编译器心情边缘(○( ＾皿＾)っHiahiahia…)

7-3 N皇后问题 (20 分)

在N * N的方格棋盘上，放置N个皇后，要求每个皇后不同行，不同列，不同左右对角线。其中N不超过10。要求：输出所有的解。算法提示：用栈求解皇后问题。

QQ图片20190404091217.png

输入格式:

输入N

输出格式:

逐行输出每一种解，用每个皇后的位置坐标表示，每个位置坐标之后均有一个空格符，输出最后一行为空行。

输入样例:

在这里给出一组输入。例如：

输出样例:

在这里给出相应的输出。例如：

1: (1,2) (2,4) (3,6) (4,1) (5,3) (6,5) 
2: (1,3) (2,6) (3,2) (4,5) (5,1) (6,4) 
3: (1,4) (2,1) (3,5) (4,2) (5,6) (6,3) 
4: (1,5) (2,3) (3,1) (4,6) (5,4) (6,2)

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int a[12][12] = { 0 }, n, b[12][12] = { 0 };
 4 int level = 0;
 5 void dfs(int x, int y)
 6 {
 7     int c[12][12] = { 0 };
 8     b[x][y] = 1;
 9     if (x <= n && y <= n) {
10         if (x == n && !a[x][y]) {
11             printf("%d:", ++level);
12             for (int i = 1; i <= n; i++)
13                 for (int j = 1; j <= n; j++) 
14                     if (b[i][j] == 1) {
15                         printf(" (%d,%d)", i, j);
16                         if (i != x)
17                             printf(" ");
18                     }
19             printf("\n");
20         }
21 
22         for (int i = 1; i <= n; i++)
23             for (int j = 1; j <= n; j++)
24             {
25                 if ((i == x || j == y || (abs(y - j) == abs(x - i)))&&(!a[i][j])) {
26                     a[i][j] = 1;
27                     c[i][j] = 1;
28                 }
29             }
30 
31         for (int i = 1; i <= n; i++)
32             if (!a[x + 1][i]) 
33                 dfs(x + 1, i);
34     }
35     for (int i = 1; i <= n; i++)
36         for (int j = 1; j <= n; j++)
37         {
38             if (c[i][j]==1)
39                 a[i][j] = 0;
40         }
41     b[x][y] = 0;
42 }
43 int main()
44 {
45 
46     scanf("%d",&n);
47     for (int i = 1; i <= n; i++)
48     {
49         dfs(1, i);
50         memset(a, 0, sizeof a);
51     }
52 }

AC代码

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[12][12] = { 0 }, n, b[12][12] = { 0 };
void dfs(int x, int y)
{
    int c[12][12] = { 0 };
    b[x][y] = 1;
    if (x <= n && y <= n) {
        if (x == n && !a[x][y]) {
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    if (b[i][j] == 1) cout << i << " " << j << " ";
            cout << endl;
        }

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                if ((i == x || j == y || (abs(y - j) == abs(x - i)))&&(!a[i][j])) {
                    a[i][j] = 1;
                    c[i][j] = 1;
                }
            }

        for (int i = 1; i <= n; i++)
            if (!a[x + 1][i]) 
                dfs(x + 1, i);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            if (c[i][j]==1)
                a[i][j] = 0;
        }
    b[x][y] = 0;
}
int main()
{

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        dfs(1, i);
        memset(a, 0, sizeof a);
    }
}

View Code

思路:一开始去网上搜了一下如何判断斜角的方法，当前斜边的点等于当前的点竖边减去横边相等。然后在bfs和暴力枚举就可以算出