【双向宽度搜索】九宫重排

点击量: 68 次

题目描述

如下面第一个图的九宫格中,放着1~8的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面,X代表空位。
1.初始状态
1    2    3
4    5    6
7    8    X
2.结束状态
1    2    3
X    4    6
7    5    8
我们把第一个图的局面记为:12345678.
把第二个图的局面记为:123.46758
显然是按从上到下,从左到右的顺序记录数字,空格记为句点。
本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1
样例输入
12345678.
123.46758
样例输出
3

思路

既然要求步数最小,优先想到的肯定是宽度搜索(BFS),但是此题又涉及到状态压缩和查重,所以我们可以借助一个map映射来存储走过的位置,那我们如何去存储每个节点呢?当然是用map<string, int>了,即绑定此条字符串的状态和已走过的步数,我们定义可以两个map映射来分别存储从头和尾开始的双向搜索分别得到的状态,当他们相遇的时候map1[string]map2[string]都不为0,则使其相加就得到了九宫格的最短路径。相对于普通的单向宽度搜索,效率会高很多,速度是相当快的,当然理解上可能还要花些时间,所以我做了很多注释。

AC代码

#include <iostream>  
#include <queue>
#include <map>
using namespace std;  
map <string, int> M1;                             //M1记录从头开始的搜索
map <string, int> M2;                             //M2记录从尾开始的搜索
typedef pair <string, int> P;                     //定义一个包含2个数据成员的结构
int dir[4] = {1, -1, 3, -3};                      //代表从右、左、下、上四个方向走一步在一维数组上的变化
string s, e;                                      //s代表起始,e 代表结束 
bool judge(int x)                                 //判断是否下一步越界
{
    if(x < 0 || x > 8) 
        return false;
    else
        return true;
}
int bfs()                                         //开整
{
    P pre1, pre2, nex;                            //头、尾结点和备胎,一个节点代表一个状态
    pre1.first = s;
    pre1.second = 0;
    pre2.first = e;
    pre2.second = 0;
    queue <P> Q1;                                 //定义队列Q1从头开始广搜
    queue <P> Q2;                                 //定义队列Q2从尾开始广搜
    M1[s] = 0;                                    //初始化映射状态,0代表着还没有步数
    M2[e] = 0;
    Q1.push(pre1);                                //头结点进栈
    Q2.push(pre2);                                //尾结点进栈
    while(!Q1.empty())
    {
        pre1 = Q1.front(); 
        Q1.pop();
        pre2 = Q2.front();
        Q2.pop();
        string s1 = pre1.first;
        int tn1 = pre1.second;                                     
        string s2 = pre2.first;
        int tn2 = pre2.second;
        int at1 = s1.find('.');                   //找到当前状态空格的位置
        int at2 = s2.find('.');
        for(int i = 0; i < 4; ++ i)               //四个方向都尝试一遍
        {
            if((i == 0 && (at1 == 2 || at1 == 5))||(i == 1 && (at1 == 3 || at1 == 6)))                                                                      //判断左右两边是否越界
                continue;
                int next = at1 + dir[i];          //走一步后所在脚下的坐标
                string str = s1;
                char t3 = str[at1];               //水桶法交换“.”的位置
                str[at1] = str[next];
                str[next] = t3;
                int step = tn1 + 1;               //步数+1
                if(judge(next))                   //再次判断这一步是否合法
                {
                    if(M1[str])                   //如果此时状态已经被记录过了,说明重步了
                    continue;
                    M1[str] = tn1 + 1;            //否则在map中记录它此时的状态
                    if(M2[str])                   //如果这一步刚好遇到了已有记录的尾部搜索map映射,则相加步数后退出
                    return M1[str] + M2[str];
                    nex.first = str;
                    nex.second = step;
                    Q1.push(nex);                 //还没找到就继续压进栈
                }
        }
        for(int i = 0; i < 4; ++ i)               //下面是尾部搜索,就不说了,综上
        {
                if((i == 0 && (at2 == 2 || at2 == 5))||(i == 1 && (at2 == 3 || at2 == 6)))
                continue;
                int next = at2 + dir[i];
                string str = s2;
                char t3 = str[at2];
                str[at2] = str[next];
                str[next] = t3;
                int step = tn2 + 1;
                if(judge(next))
                {
                    if(M2[str])
                    continue;
                    M2[str] = tn2 + 1;
                    if(M1[str])
                    return M1[str] + M2[str];
                    nex.first = str;
                    nex.second = step;
                    Q2.push(nex);
                }
        }
    }
    return -1;                                    //没有可走的道路,返回-1
} 
int main()  
{  
    int ans = 0;
    cin >> s >> e;
    if(s != e)                                    //如果初始状态和结束状态都一样就没必要搜了
    ans = bfs();
    if(ans == -1)
        cout << "-1" << endl;
    else
        cout << ans << endl;
    return 0;                                     //不长不长,走你(づ ̄ 3 ̄)づ
}   
 最大组合数
【贪心】田忌赛马 
上一篇:最大组合数
下一篇:【贪心】田忌赛马


点击开始摧毁这篇水文,方向键控制,空格发弹,Esc退出


pao.gifchui.gifpen.gifpai.gifhan.pngxia.pnghuaji.pngwa.pngbi.pngxin.pngleng.pnghua.pngmeng.pngjingya.pngqian.pnghan1.pngquan.pngnu.pnggan.pngdaxiao.pngku.pngqu.png



Proudly published with Typecho))).

Living (*>ω<*)

Copyright @ 2019 Kira's Blog



哎呀,穷死了,求赞赏!

支付宝
微信
QQ
0:00