bfs

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
using namespace std;
int step = 0;
// 每次要不就是和左边交换要不就是和右边交换
int dirs[4] = {-2, -1, 1, 2};
void bfs(string source, string target){
    queue<string> q;
    set<string> visited;
    q.push(source);
    visited.insert(source);
    while(!q.empty()){
        step += 1;
        int qsize = q.size();
        for(int i = 0; i < qsize; i++){
            string t = q.front();
            q.pop();
            if(t == target) return;
            int pos = t.find(' ');
            for(int i = 0; i < 4; i++){
                string next = t;
                swap(next[(pos + dirs[i] + 9) % 9], next[pos]);
                if(visited.count(next)){
                    continue;
                }
                cout << next << endl;
                q.push(next);
                visited.insert(next);
            }
        }
    }
}
int main(){
    // 空格代表空盘子
    bfs("12345678 ", "87654321 ");
    cout << step << endl;
    return 0;
}