AOJ 0121 Seven Puzzle bfs

//https://blog.csdn.net/qq_33929112/article/details/52454779
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<map>
#include<string>
#include<algorithm>
using namespace std;

map<string, int> dp;
int dir[4] = {-1,1,4,-4}; // 4 个方向

bool in(int a, int b)
{
    if(a+b < 0 || a+b > 7) return false;
    if(a == 3 && b == 1 || a == 4 && b == -1) return false;
    return true;
}

void bfs()
{
    queue<string> que;
    que.push("01234567");
    dp["01234567"] = 0;
    while(!que.empty())
    {
        string s = que.front();
        que.pop();
        int index;
        for(int i = 0;  i < 8; i++) if(s[i] == ‘0‘) index = i;
        for(int i = 0; i < 4; i++)
        {
            if(in(index, dir[i]))
            {
                string tmp = s;
                int ni = index+dir[i];
                swap(tmp[ni], tmp[index]);
                if(dp.find(tmp) == dp.end())  //找不到
                {
                    dp[tmp] = dp[s]+1;
                    que.push(tmp);
                }
            }
        }
    }
}


int main()
{
    bfs();
    string s;
    while(getline(cin, s))
    {
        s.erase(remove(s.begin(), s.end(), ‘ ‘), s.end());
        cout << dp[s] << endl;
    }
    system("pause");
    return 0;
}

AOJ 0121 Seven Puzzle bfs

原文：https://www.cnblogs.com/znk97/p/14130840.html