AcWing 195. 骑士精神

双向BFS (广搜) \(O(8 ^ 7)\)

看到没有双向BFS的题解我就过来了

这道题也可以用双向\(BFS\)来做，时间复杂度与\(IDA*\)不相上下。

双向\(BFS\)的实现有多种：

把初始状态和目标状态扔在一个队列里，每次从队列里搞出来一个扩展
把初始状态和目标状态扔在两个队列里，每次选一个队列中元素少的拓展。
把初始状态和目标状态扔在两个队列里，每次分别从两个队列中取出一个元素拓展。

这里使用了方法\(1\)。

时间复杂度分析：每次会扩展\(8\)个状态，最多扩展\(\lfloor\frac{15}{2}\rfloor = 7\)次（到第八次如果还找不到则肯定超过限制的\(15\)步，答案则无需扩展），所以复杂度是\(O(8 ^ 7)\)的

具体实现方面看代码。

C++ 代码

#include <iostream>

#include <cstdio>

#include <unordered_map>

#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;

int dx[8] = {1, 1, -1, -1, 2, 2, -2, -2};

int dy[8] = {-2, 2, 2, -2, 1, -1, 1, -1};

//移动方向的打表

int n;

//状态结构体

struct Node{

    int v[5][5], f, x, y;

    //f = 0 表示从初始状态出发， f = 1 表示从目标状态出发

}s, t, u;

unordered_map<int, int> step[2][30];

// 记录每个状态对应的位置。

int goal[5][5] = {

    {1, 1, 1, 1, 1},

    {0, 1, 1, 1, 1},

    {0, 0, 2, 1, 1},

    {0, 0, 0, 0, 1},

    {0, 0, 0, 0, 0}

};

//目标状态打表

int start[5][5];

//get(x) 获取状态x的步数

int get(Node x){

    int  sum = 0;

    //把一个位置状态转移成一个二进制数，比较方便。

    for(int i = 0; i < 5; i++)

        for(int j = 0; j < 5; j++)

            if(x.v[i][j] == 1)

                sum |= 1 << (i * 5 + j);

    if(step[x.f][x.x * 5 + x.y].count(sum) == 0) return INF;

    return step[x.f][x.x * 5 + x.y][sum];

}

//set() 设置状态x的步数

void set(Node x, int val){

    int sum = 0;

    for(int i = 0; i < 5; i++)

        for(int j = 0; j < 5; j++)

            if(x.v[i][j] == 1)

                sum |= 1 << (i * 5 + j);

    step[x.f][x.x * 5 + x.y][sum] = val;

}

int bfs(){

    queue<Node> q;

    q.push(s); q.push(t);

    set(s, 0);

    set(t, 0);

    while(!q.empty()){

        Node u = q.front(); q.pop();

        //找到同位置的另一状态

        Node l = u; l.f = u.f ^ 1;

        //如果相遇，代表已经找到一条最短的路径

        if(get(u) + get(l) <= 15)

            return get(u) + get(l);

        //说明所有状态已经都至少走了 8 步， > 最大限制 15

        if(get(u) >= 8) break;

        l.f = u.f;

        for(int i = 0; i < 8; i++){

            int nx = u.x + dx[i], ny = u.y + dy[i];

            if(nx < 0 || nx >= 5 || ny < 0 || ny >= 5) continue;

            swap(l.v[u.x][u.y], l.v[nx][ny]);

            l.x = nx, l.y = ny;

            if(get(u) + 1 < get(l)){

                set(l, get(u) + 1);

                q.push(l);

            }

            //还原现场

            swap(l.v[u.x][u.y], l.v[nx][ny]);

        }

    }

    return -1;

}

int main(){

    for(int i = 0; i < 5; i++)

        for(int j = 0; j < 5; j++)

            t.v[i][j] = goal[i][j];

    t.f = 1; t.x = 2; t.y = 2;

    int T; scanf("%d", &T);

    while(T--){

        for(int i = 0; i < 2; i++)

            for(int j = 0; j < 30; j++)

                step[i][j].clear();

        for(int i = 0; i < 5; i++){

            for(int j = 0; j < 5; j++){

                char x; cin >> x;

                if(x == '*')s.x = i, s.y = j, s.v[i][j] = 2;

                else s.v[i][j] = x - '0';

            }

        }

        s.f = 0;

        printf("%d\n", bfs());

    }

    return 0;

}

巴特西

AcWing 195. 骑士精神

双向BFS (广搜) \(O(8 ^ 7)\)

时间复杂度分析：每次会扩展\(8\)个状态，最多扩展\(\lfloor\frac{15}{2}\rfloor = 7\)次（到第八次如果还找不到则肯定超过限制的\(15\)步，答案则无需扩展），所以复杂度是\(O(8 ^ 7)\)的

C++ 代码

最新文章

热门文章