算法bfs

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <queue>


using namespace std;


struct State{
    vector<string> states; //记录当前这个样子
    int moves; //经过了几次得到现在这个states
};

int bfs(vector<string> &start, vector<string> &finlly){
    queue<State> q;
    //定义一个visited记录是否被访问过
    unordered_set<string> visited;

    //转换成字符串
    string finlly_str = "";
    // for (auto s : start) start_str += s;
    for (auto s : finlly) finlly_str += s;

    //放入队列, 移动次数为0
    q.push({start, 0});

    //移动的四个位置
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    while(!q.empty()){
        auto current = q.front();
        q.pop();

        //
        string start_str = "";
        for (auto s : current.states) start_str += s;

        if (start_str == finlly_str) return current.moves;

        //四个方向移动
        for (int i = 0; i < 4; i ++ ){
            for (int j = 0; j < 4; j ++ ){
                //如果当前有玩具，移动
                if (current.states[i][j] == '1'){
                    for (int k = 0; k < 4; k ++ ){
                        int nx = i + dx[k], ny = j + dy[k];

                        //越界判断和是否为 当前位置是否为0
                        if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4 && current.states[nx][ny] == '0'){
                            //交换
                            swap(current.states[i][j], current.states[nx][ny]);

                            string new_str = "";
                            for (auto s : current.states) new_str += s;
                            //查看是否被记录过，没有被记录就记录并加入
                            if (visited.find(new_str) == visited.end()){
                                visited.insert(new_str);
                                // q.push(State{current.states, current.moves + 1});
                               q.push({current.states, current.moves + 1});
                            }
                            //复原，下个方向
                            swap(current.states[i][j], current.states[nx][ny]);
                        }
                    }
                }
            }
        }
    }

    return -1;//没有找到解
}

int main(){

    vector<string> start(4), finlly(4); //定义开始和结束，定义一个vector中里面类型为string，大小为4个的空串的容器
    //输入开始，和目标
    for (int i = 0; i < 4; i ++ ) cin >> start[i];

    //跳过空行影响
    cin.ignore();

    for (int i = 0; i < 4; i ++ ) cin >> finlly[i];

    //使用bfs
    int res = bfs(start, finlly);
    cout << res << endl;
    return 0;
}