深度优先搜索初析(2)

深度优先搜索初析(2)

/ 0评 / 1497次 / 2

——以“八皇后”为例

题目描述

一个如下的   \(6 × 6\)   的跳棋棋盘,有六个棋子被放置在棋盘上,使得每行、每列有且只有一个,每条对角线(包括两条主对角线的所有平行线)上至多有一个棋子。

上面的布局可以用序列 2 4 6 1 3 5 来描述,第 ii 个数字表示在第 ii 行的相应位置有一个棋子,如下:

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出,解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。

输入格式

一行一个正整数 nn,表示棋盘是   \(n × n\)  大小的。

输出格式

前三行为前三个解,每个解的两个数字之间用一个空格隔开。第四行只有一个数字,表示解的总数。

题目分析

深搜经典题,深搜思路大致是按列遍历,从第一行往下开始走

比方说我们在第一行第一列放置一枚棋子,进入第二行,显然第二行的第一列和第二列都不符合,那就放到第三列,以此类推。

那么也就是说,本题的核心其实是写出一个check函数用以判断在当前位置放置一个棋子是否合法。由于不能在同一行同一列同一对角线。

同一行与同一列的去重其实好办,难度就是在对角线的判断,我这里使用了两个数组进行暴力处理,也就是记录这一条对角线是否有放置,粗暴但有效

Accepted Code

/*
 * @Author: Gehrychiang
 * @Date: 2019-12-12 22:19:26
 * @LastEditors  : Please set LastEditors
 * @LastEditTime : 2020-01-31 12:21:40
 * @Website: www.yilantingfeng.site
 * @E-mail: gehrychiang@aliyun.com
 */
#include <bits/stdc++.h>
using namespace std;
int n;
int cnt=0;//记录情况总数
int table[14][14] = {0};//保存皇后地图
int zuoxie[28] = {0};//记录左斜方向
int youxie[28] = {0};//记录右斜方向
bool check(int x, int y)//检查在当前位置填充是否合法
{
    //列
    for (int i = 0; i < x; i++)
    {
        if (table[i][y] == 1)
            return false;
    }
    //斜
    if (zuoxie[x + y] != 0 || youxie[x - y + n - 1] != 0)
        return false;
    return true;
}
//深搜思路是在第x行遍历 列的1到n 能放进就进入下一行
void dfs(int x) //x行
{
    if (x == n)//一种情况已经结束,此时将结果输出,并返回上一层
    {
        if (cnt < 3)
        {
            for (int u = 0; u < n; u++)
            {
                for (int v = 0; v < n; v++)
                {
                    if (table[u][v] == 1)
                        cout << v + 1 << " ";
                }
                
            }
            cout << endl;
        }
        ++cnt;
        return;
    }

    for (int y = 0; y < n; y++)
    {
        if (check(x, y))
        {
            //情况改变,去重并记录
            ++zuoxie[x + y];
            ++youxie[x - y + n - 1];
            table[x][y] = 1;
            dfs(x + 1);
            //回到当前节点,回溯
            --zuoxie[x + y];
            --youxie[x - y + n - 1];
            table[x][y] = 0;
        }
    }
    return;
}
int main()
{
    cin >> n;
    dfs(0);
    cout << cnt << endl;
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.63967