宽搜问题

1.八数码问题

首先针对题意得简述是给定初始状态和目标状态，状态中数字0的位置和与其相邻的四个位置可以交换，通过不断交换数字0的位置使其得到目标状态，并统计交换的次数。我们可以将这个问题抽象化成图论问题，我们把初始状态和目标状态看成图中的节点，那么初始状态可以变化得到的状态是初始状态这个节点的邻接点，如下图所示，那么我们可以对这个图做一遍最短路便可以得到我们想要的答案。那么剩下需要解决的问题就只有怎么将一个状态保存下来以及如果记录过程中到达某一节点的距离，保存到一个节点当中。这里我们可以将三行整合成一个字符串，然后假设当前这个字符串中数字0的位置是k，那么我们可以通过x=k/3，y=k%3的方法得到他在3*3中的位置，那么由此便可以将状态存储下来，当遍历其邻接点的时候也可以完成下一个状态的推导。那么针对记录距离我们可以使用哈希表去记录转移到对应字符串(状态)时的距离，unordered_map<string, int > d。

/*
在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要几步能到达目标状态（用0表示空格）：
初始状态的步数就算1
【输入格式】
第一个3*3的矩阵是原始状态；
第二个3*3的矩阵是目标状态。
【输出格式】
输出移动所用最少的步数。
【样例1输入】
2 8 3
1 6 4
7 0 5
1 2 3
8 0 4
7 6 5
【样例1输出】
6
【样例2输入】
2 8 3
1 6 4
7 0 5
0 1 2
3 4 5
8 7 6
【样例2输出】
18
*/

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;
string endstate="";
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int bfs(string start);

int main()
{
    string start;
    for(int i=0;i<9;++i)
    {
        char c;
        cin>>c;
        start+=c;
    }
    for(int i=0;i<9;++i)
    {
        char c;
        cin>>c;
        endstate+=c;
    }
    cout<<bfs(start)+1<<endl;

    return 0;
}

int bfs(string start)
{
    //string end="123456780";
    queue<string> q;
    unordered_map<string,  int> d;
    q.push(start);
    d[start]=0;

    while(q.size())
    {
        auto t=q.front();
        q.pop();
        int distance=d[t];
        if(t==endstate)
            return distance;
        //状态转移
        int k=t.find('0');
        int x=k/3,y=k%3;
        for(int i=0;i<4;++i)
        {
            int a=x+dx[i];
            int b=y+dy[i];
            if(a>=0&&a<3&&b>=0&&b<3)
            {
                swap(t[k],t[3*a+b]);
                if(!d.count(t))
                {
                    d[t]=distance+1;
                    q.push(t);
                }
                swap(t[k],t[3*a+b]);
            }
        }
    }
    return -1;
}

2.魔板

这一题与上一题的思想类似，我们将每一个状态看成图中的一个节点，并且使用一个字符串来存储当前的状态，每一个节点的邻接点是通过ABC三个操作可以得到的新状态，由此可以构建出一个图，那对这个图进行bfs便可以得到需要的答案，但是这道题目当中需要记录得到目标状态进行的操作，那么我们可以将搜索的过程记录下来。我们转移到下一个状态的时候，我们记录一下通过当前状态可以得到下一个转移的新状态。同理我们这里的距离使用哈希表来记录每一个对应的状态对应的距离。

/*
Rubik 先生在发明了风靡全球的魔方之后，又发明了它的二维版本——魔板。
这是一张有 8 个大小相同的格子的魔板：
1 2 3 4
8 7 6 5
我们知道魔板的每一个方格都有一种颜色。
这 8 种颜色用前 8 个正整数来表示。
可以用颜色的序列来表示一种魔板状态，规定从魔板的左上角开始，沿顺时针方向依次取出整数，构成一个颜色序列。
对于上图的魔板状态，我们用序列 (1,2,3,4,5,6,7,8) 来表示，这是基本状态。
这里提供三种基本操作，分别用大写字母 A，B，C 来表示（可以通过这些操作改变魔板的状态）：
A：交换上下两行；
B：将最右边的一列插入到最左边；
C：魔板中央对的4个数作顺时针旋转。
下面是对基本状态进行操作的示范：
A：
8 7 6 5
1 2 3 4
B：
4 1 2 3
5 8 7 6
C：
1 7 2 4
8 6 3 5
对于每种可能的状态，这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到特殊状态的转换，输出基本操作序列。
注意：数据保证一定有解。
输入格式
输入仅一行，包括 8 个整数，用空格分开，表示目标状态。
输出格式
输出文件的第一行包括一个整数，表示最短操作序列的长度。
如果操作序列的长度大于0，则在第二行输出字典序最小的操作序列。
数据范围
输入数据中的所有数字均为 1 到 8 之间的整数。
输入样例：
2 6 8 4 5 7 3 1
输出样例：
7
BCABCCB
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <unordered_map>
using namespace std;
char g[2][4];
unordered_map<string, pair<char, string>> pre;
unordered_map<string, int> dist;
queue<string> q;
void set(string state);
string get();
string move0(string state);
string move1(string state);
string move2(string state);
int bfs(string start, string end);

int main()
{
    int x;
    string start, end;
    for(int i=0;i<8;++i)
    {
        cin>>x;
        end+=(x+'0');
    }
    start="12345678";
    int step=bfs(start, end);
    string res;
    while(end!=start)
    {
        res+=pre[end].first;
        end=pre[end].second;
    }
    reverse(res.begin(),res.end());
    cout<<step<<endl;
    if(step>0)
        cout<<res<<endl;
    return 0;
}

void set(string state)
{
    for(int i=0;i<4;++i)
        g[0][i]=state[i];
    for(int i=7, j=0; j<4; --i, ++j)
        g[1][j]=state[i];    
}

string get()
{
    string res;
    for(int i=0;i<4;++i)
        res+=g[0][i];
    for(int i=3;i>=0;--i)
        res+=g[1][i];
    return res;
}

string move0(string state)
{
    set(state);
    for(int i=0;i<4;++i)
        swap(g[0][i],g[1][i]);
    return get();
}

string move1(string state)
{
    set(state);
    for(int i=3;i>0;--i)
    {
        swap(g[0][i],g[0][i-1]);
        swap(g[1][i],g[1][i-1]);
    }
    return get();
}

string move2(string state)
{
    set(state);
    char t=g[0][1];
    g[0][1]=g[1][1];
    g[1][1]=g[1][2];
    g[1][2]=g[0][2];
    g[0][2]=t;
    return get();
}

int bfs(string start, string end)
{
    if(start==end)
        return 0;
    q.push(start);
    while(!q.empty())
    {
        auto t=q.front();
        q.pop();
        dist[start]=0;
        string ans[3];
        ans[0]=move0(t);
        ans[1]=move1(t);
        ans[2]=move2(t);
        for(int i=0;i<3;++i)
        {
            if(!dist.count(ans[i]))
            {
                dist[ans[i]]=dist[t]+1;
                pre[ans[i]]={'A'+i, t};
                q.push(ans[i]);
                if(ans[i]==end)
                    return dist[end];
            }
        }
    }
    
    return -1;
}

3.巧妙取量

针对这题，仅提供三个容器，并且每次只能将一个容器中的油倒入另一个容器，所以由每个状态可以得到的新的状态只有六个，将这个反映在图中即可发现如下图

那么我们和上面的题一样用哈希表记录一个状态对应由初始状态转换过来的距离，那么由此对该图进行bfs遍历便可得到答案，但是这题涉及到如何取存储状态，最简便的方法便是使用结构体去存储每一个状态，但是哈希表不可以直接使用用户自定义类型去充当参数定义key-value值，针对于map需要重载<运算符，对于unordered_map请参照该博客：(16条消息) C++ STL：unordered_map 自定义键值类型_爱吃柚子的好奶罐-CSDN博客_unordered_map自定义hash函数

/*
【题目描述】 
有三个容器，容量分别为 a,b,c（a> b > c ),一开始a装满油，现在问是否只靠abc三个容器量出k升油。
如果能就输出“yes”，并且说明最少倒几次，否则输出“no”。
例如：10升油在10升的容器中，另有两个7升和3升的空容器，要求用这三个容器倒油，
使得最后在abc三个容器中有一个刚好存有5升油，问最少的倒油次数是多少？
（每次倒油，A容器倒到B容器，或者A内的油倒完，或者B容器倒满。 ）
  10 7 3 
（10 0 0） 
 （3 7 0）:第一次 
 （3 4 3）：第二次 
 （6 4 0）：第三次 
 （6 1 3）：第四次 
 （9 1 0）：第五次 
 （9 0 1）：第六次 
 （2 7 1）：第七次 
 （2 5 3）：第八次，出现5了。
【输入格式】
输入有多组测试数据。
输入a，b，c, k四个正整数( 100 a > b > c > = 1 , 1 < = k < 100 )
【输出格式】
如果能得到k就输出两行
第一行“yes”，第二行为最少的次数，否则输出“no”
【样例输入】
10 7 3 5
【样例输出】
yes
8
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <map>
#include <queue>
using namespace std;
int x, y, z, k;
struct Node
{
    int a, b, c;
    Node(int _a, int _b, int _c)
    {
        a=_a, b=_b, c=_c;
    }
    bool operator < (const Node& N) const
    {
        if(a!=N.a)
            return a<N.a;
        else if(b!=N.b)
            return b<N.b;
        else
            return c<N.c;
    }
};
bool exist(Node u);
int bfs(Node start, int u);

int main()
{
    while(cin>>x>>y>>z>>k) {
        if(k>x)
        {
            puts("no");
            return 0;
        }
        Node start(x, 0, 0);
        int res = bfs(start, k);
        if (res != -1) {
            puts("yes");
            cout << res << endl;
        } else
            puts("no");
    }
    return 0;
}

bool exist(Node u)
{
    if(u.a==k||u.b==k||u.c==k)
        return true;
    return false;
}

int bfs(Node start, int u)
{
    map<Node, int> dist;
    queue<Node> q;
    q.push(start);
    dist[start]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(exist(t))
            return dist[t];
        //六种情况
        //1.a->b
        Node n(0, 0, 0);
        int v=min(t.a, y-t.b);
        if(v>0)
        {
            n.a=t.a-v;
            n.b=t.b+v;
            n.c=t.c;
            if(!dist.count(n))
            {
                dist[n]=dist[t]+1;
                q.push(n);
            }
        }
        //2.a->c
        v=min(t.a,z-t.c);
        if(v>0)
        {
            n.a=t.a-v;
            n.c=t.c+v;
            n.b=t.b;
            if(!dist.count(n))
            {
                dist[n]=dist[t]+1;
                q.push(n);
            }
        }
        //3.b->a
        v=min(t.b, x-t.a);
        if(v>0)
        {
            n.b=t.b-v;
            n.a=t.a+v;
            n.c=t.c;
            if(!dist.count(n))
            {
                dist[n]=dist[t]+1;
                q.push(n);
            }
        }
        //4.b->c
        v=min(t.b, z-t.c);
        if(v>0)
        {
            n.b=t.b-v;
            n.c=t.c+v;
            n.a=t.a;
            if(!dist.count(n))
            {
                dist[n]=dist[t]+1;
                q.push(n);
            }
        }
        //5.c->a
        v=min(t.c, x-t.a);
        if(v>0)
        {
            n.c=t.c-v;
            n.a=t.a+v;
            n.b=t.b;
            if(!dist.count(n))
            {
                dist[n]=dist[t]+1;
                q.push(n);
            }
        }
        //6.c->b
        v=min(t.c, y-t.b);
        if(v>0)
        {
            n.c=t.c-v;
            n.b=t.b+v;
            n.a=t.a;
            if(!dist.count(n))
            {
                dist[n]=dist[t]+1;
                q.push(n);
            }
        }
    }
    return -1;
}

4.海上舰队Ⅱ——救援任务

针对于该题我们发现其只是最简单的迷宫问题，从起点开始搜索，若是可以搜的重点，则此时搜索到的距离就是最短距离，若是搜索不到终点，则说明这两个点不在同一个舰队当中。

/*
【题意】
广阔的大海地图可以由矩形阵列表示。 
矩阵的元素由数字0和1组成。0表示海水。数字1代表军舰。 
同一舰队的定义为沿军舰数字上下左右还是军舰数字1则为同一舰队。 
求给定矩形阵列的舰队个数。如:矩阵 
0111100011
1011110100
1011100111
0000000011
有4个舰队。 
其中有艘军舰发生故障，负责救援的人员从固定的救援军舰赶往故障处。处于安全考虑，救援人员只能通过舰队内部到达故障点。 
【输入格式】 
第一行两个整数n，m （1 < = n，m< ＝ 1000） 
下来是n×m矩阵 
下来一行K（1 < = K < =2000) ，代表下来K行有K个询问。每行为X1,Y1,X2,Y2代表两艘军舰的海上坐标。 
【输出格式】
如果两艘军舰属于同一舰队那么输出它们之间最短的内部距离，若两艘军舰不属于同一舰队，那么请输出"Impossible". 
注意： 舰队由军舰构成。^_^ 
【样例输入】
4 10
0111100011
1011110100
1011100111
0000000011
2
1 3 2 6
1 3 4 10
【样例输出】
4
Impossible
*/

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 1010;
int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};
char g[N][N];
int dist[N][N];
int n, m, k;
int bfs(int x1, int y1, int x2, int y2);

int main()
{
    cin>>n>>m;
    for (int i = 0; i < n; ++ i)
        cin>>g[i];
    cin>>k;
    int x1, y1, x2, y2;
    while(k--)
    {
        memset(dist, -1, sizeof dist);
        cin>>x1>>y1>>x2>>y2;
        --x1, --y1, --x2, --y2;
        int t=bfs(x1, y1, x2, y2);
        if(t!=-1)
            cout<<t<<endl;
        else
            puts("Impossible");
    }
    return 0;
}
int bfs(int x1, int y1, int x2, int y2)
{
    if(x1==x2 && y1==y2)
        return 0;
    queue<PII> q;
    q.push({x1, y1});
    dist[x1][y1]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t.x==x2&&t.y==y2)
            return dist[t.x][t.y];
        for (int i = 0; i < 4; ++ i)
        {
            int a=t.x+dx[i], b=t.y+dy[i];
            if(a>=0 && a<n && b>=0 && b<m && dist[a][b]==-1 && g[a][b]=='1')
            {
                dist[a][b]=dist[t.x][t.y]+1;
                q.push({a, b});
            }
        }
    }
    return -1;
}

5.基因重组

针对每一个状态记录为一个字符串，将每一个状态看成图中的一个节点，每一个状态经过两个操作的直接邻接点有两个，可以转移的两个新的状态，由此对该图进行遍历即可得到最少操作次数。

/*
【题目描述】 
众所周知,一个基因可被视为是一种序列,包括了4种核苷酸，可由四个字母表示,A,C、G、T。
一个工程师在进行遗传基因项目的研究，他有这样一项工作： 
例如有一个基因“ATCC”。工程师想重新整理它变成“CTCA”。
他能使用两种操作：
（1）交换基因的前两个字母；
（2）移动基因的第一个字母到最后。例如“ATCC”利用操作2可以变成“TCCA”，利用操作1可以变成“CTCA”。
你的任务是写一个程序找出将第一种基因变换成第二种情况的最少操作次数。 
【输入格式】 
多组数据。每组数据第一行为正整数N表示基因的长度（1≤N≤12）。第二行为原基因序列，第三行为目标基因序列。对于每一种字母，这两个基因具有相同的数目。 
最后一行为数字0，表示输入结束。 
【输出格式】 
每组数据输出一行，输出最少操作步骤。 
【样例输入】
4
ATCC
CTCA
4
ATCG
GCTA
4
ATCG
TAGC
0
【样例输出】
2
4
6
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <unordered_map>
#include <queue>
using namespace std;
int n;
int bfs(string start, string ed);

int main()
{
    while(cin>>n, n)
    {
        string start, ed;
        cin>>start>>ed;
        cout<<bfs(start, ed)<<endl;
    }
    return 0;
}

int bfs(string start, string ed)
{
    unordered_map<string, int> dist;
    queue<string> q;
    q.push(start);
    dist[start]=0;
    while(q.size())
    {
        auto t=q.front();
        q.pop();
        if(t==ed)
            return dist[ed];
        int distance=dist[t];
        string ans[2];
        ans[0]=ans[1]=t;
        swap(ans[0][0], ans[0][1]);
        if(!dist[ans[0]])
        {
            dist[ans[0]]=distance+1;
            q.push(ans[0]);
        }
        for (int i = 1; i < ans[1].size(); ++ i)
            swap(ans[1][i-1], ans[1][i]);
        if(!dist[ans[1]])
        {
            dist[ans[1]]=distance+1;
            q.push(ans[1]);
        }
    }
    return -1;
}