美文网首页
深搜回溯(八皇后,单词方阵)

深搜回溯(八皇后,单词方阵)

作者: 鲸尾上若叶 | 来源:发表于2019-12-04 12:41 被阅读0次

1.要说八皇后问题,具体问题就不在描述了
第一种:用矩阵存储棋盘map[n][n]:一行一行(或一列一列)放棋子。
代码如下

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;

int map[20][20];
int cnt = 0;
int n;

bool check(int x, int y)
{
    for(int i = 0; i < n; i++)
    {
        if(map[x][i]) return false;//判断行 
        if(map[i][y]) return false;//判断列 
    }
    for(int i = 0; i < n; i++)//判断斜列 
    {
        for(int j = 0; j < n; j++)
        {
            if(abs(i-x) == abs(j-y))
                if(map[i][j])
                    return false;
        }
    }
    //都没有问题 
    return true;
}
//打印map 
void print_map()
{
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            cout << map[i][j] << " ";
        cout << endl;
    }
    cout << endl;
}

void dfs(int col)//最开始传入0, 表示第一列 
{
    for(int i = 0; i < n; i++)
    { 
        if(check(i, col))// 第一列看看有没有那个点可以放皇后 
        {
            if(col == n-1) //表示最后一列,皇后放置完毕 
            {
                map[i][col] = 1;  //放皇后 
                print_map();  //打印map 
                cnt++;  //记录解的个数 
                map[i][col] = 0;  //恢复 
            }
            else 
            {
                map[i][col] = 1; //放皇后 
                dfs(co+1);  //进入下一列 
                map[i][col] = 0; //恢复 
            }
        }
    }
}

int main()
{
    memset(map, 0, sizeof(map));
    cin >> n;
    dfs(0);
    cout << cnt;
}

回溯最重要的是每次要恢复已经放置的皇后。
缺点:每个点都去check,意味着每个点都要去遍历整张map,太慢,所以有了第二种。

第二种:用一个map[n][n]存储棋盘,四个数组表示(棋盘每个位置的行,列, 斜向左列, 斜向右列)有没有放置皇后,虽然不直观,多了四个一维数组,但是高效。
代码如下:

#include<bits/stdc++.h>
using namespace std;

bool row[100+5], col[100+5], lef[100+5], rig[100+5];  //分别为行,列, 斜向左列和斜向右列
bool chess[20][20];
int n, k = 0;

void print_answer()
{
    //print省略
    k++;
}

void dfs(int ro)  //从第一行开始
{
    for(int i = 0; i < n; i++)
    {       //给出一个点
        if(!row[ro] && !col[i] && !lef[ro+i] && !rig[i-ro+n])  //如果这个点所在的行,列,斜向左列,斜向右列都没有其他皇后
        {
            row[ro] = true; 
            col[i] = true;
            lef[ro+i] = true;
            rig[i-ro+n] = true;
            chess[ro][i] = true;  //放置皇后
            if(ro == n-1)
                print_answer();
            else dfs(ro+1);
            row[ro] = false;
            col[i] = false;
            lef[ro+i] = false;
            rig[i-ro+n] = false;
            chess[ro][i] = false; // 恢复皇后
        }
    }
}

int main()
{
    memset(row, false, sizeof(row)); 
    memset(col, false, sizeof(col));
    memset(lef, false, sizeof(lef));
    memset(rig, false, sizeof(rig));
    cin >> n;
    dfs(0);
    cout << k;
    return 0;
}

由于每次查找check都是O(1),自然而然高效率了。

2.单词方阵:题目描述
给一n×n的字母方阵,内可能蕴含多个“yizhong”单词。单词在方阵中是沿着同一方向连续摆放的。摆放可沿着 8 个方向的任一方向,同一单词摆放时不再改变方向,单词与单词之间可以交叉,因此有可能共用字母。输出时,将不是单词的字母用*代替,以突出显示单词。例如:

输入:
    8                     输出:
    qyizhong              *yizhong
    gydthkjy              gy******
    nwidghji              n*i*****
    orbzsfgz              o**z****
    hhgrhwth              h***h***
    zzzzzozo              z****o**
    iwdfrgng              i*****n*
    yyyygggg              y******g

思路:遍历方阵,找到首字母'y',进入深搜模式,深搜分两个模块:第一是向八个方向找,找到下一个字母'i'。第二个模块是已经找到第二个字母,即确定了方向,然后向确定的方向深搜。

由于在查找完整单词的过程中需要标记单词位置,即边查找便标记(为了输出),查找到了完整的单词还不能抹掉(因为抹掉就不能输出了)。 就会产生一个问题:单词查找了一半发现错误,怎么把之前已经标记了的位置抹掉? 这里有一个新的技巧就是:深搜函数使用bool类型,只有这一整个单词查找成功,这个单词每个字母的所在位置才标记,即:

if(dfs(next_letter)) return true;

但是在深搜的第一个模块却不能直接return true。 因为要尝试8个方向,如果一个方向查到到了,就直接return true了,就会漏掉剩下的情况。因此,不妨在函数开始初始化一个bool类型的标记,如下:

bool dfs(char letter)
{
    bool ok = false;
    ......
    if(dfs(next_letter) ok = true;
    ......

    return ok;
}

就可以完美解决问题。奉上代码:

#include<bits/stdc++.h>
using namespace std;

int n;
char num[100+5][100+5];
bool have[100+5][100+5];
string s = "yizhong";

bool dfs(int i, int x, int y, int d1, int d2)  //参数分别是字母下标(用s[i])得到该字母,开始深搜的开始位置x, y; 以及第二模块中确定的方向d1, d2
{
    bool ok = false;
    if(i == 7) return true;
    if(i == 1)   //第一模块,找下一字母,确定方向
        for(int k1 = -1; k1 <= 1; k1++)
            for(int k2 = -1; k2 <= 1; k2++)
            {
                if(!k1 && !k2) continue;
                int x1 = x + k1, y1 = y + k2;
                if(x1 >= 0 && x1 < n && y1 >= 0 && y1 < n)
                {
                    if(num[x1][y1] == s[i])
                    {
                        if(dfs(i+1, x1, y1, k1, k2))   如过深搜链查找完成,全部return ok,标记改单词的所有字母的位置
                        {
                            have[x1][y1] = true;
                            ok = true;
                        }
                    }
                }
            }
    else //第二模块,按照确定方向找下一个字母
    {
        int x1 = x+d1, y1 = y+d2;
        if(x1 >= 0 && x1 < n && y1 >= 0 && y1 < n)
            if(num[x1][y1] == s[i]) 
            {
                if(dfs(i+1, x1, y1, d1, d2))
                {
                    have[x1][y1] = true;
                    return true;
                }
            }
    }
    return ok;
} 

int main()
{
    memset(have, false, sizeof(have));
    cin >> n;
    for(int i = 0; i < n; i++)
        scanf("%s", num[i]);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(num[i][j] == 'y')  //开始深搜
            {
                if(dfs(1, i, j, 0, 0)) have[i][j] = true;
            }
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            if(have[i][j]) cout << num[i][j];
            else cout << "*";
        cout << endl;
    }
}

相关文章

  • 深搜回溯(八皇后,单词方阵)

    1.要说八皇后问题,具体问题就不在描述了第一种:用矩阵存储棋盘map[n][n]:一行一行(或一列一列)放棋子。代...

  • 【洛谷 P1219】八皇后

    八皇后(题目链接) 思路 典型的深搜回溯问题 代码

  • 深度搜索与回溯

    深度搜索与回溯法的区别 回溯法 = 深搜 + 剪枝。一般大家用深搜时,或多或少都会剪枝。深搜一般用递归实现,比较简...

  • 47. 全排列 II

    思路 排序,人为规定顺序去重。 深搜+回溯

  • LeetCode 51. N-Queens

    Leetcode : N-QueensDiffculty:Hard N皇后问题,对八皇后问题的扩展,典型的回溯法算...

  • 八皇后-回溯算法

    在之前的文章里,我们介绍了图相关的一些算法。今天我们通过N皇后问题来讨论下回溯算法。 首先,我们先介绍下什么是回溯...

  • 回溯算法 八皇后

    什么是回溯算法 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条...

  • [深搜回溯]24点

    题目描述:24点是一个有趣的扑克牌游戏。发4张牌,然后计算是否能够算出24点来。(不考虑有括号的算式,输出计算式将...

  • 八皇后问题

    采用试探回溯策略,通过栈记录查找结果,实现八皇后问题求解。 测试代码

  • N皇后

    回溯法核心代码: n皇后问题回溯法

网友评论

      本文标题:深搜回溯(八皇后,单词方阵)

      本文链接:https://www.haomeiwen.com/subject/kuxkgctx.html