【BFS】八数码 - 最少交换次数

题目

845. 八数码

---

在一个 $3×3$ 的网格中，$1 \sim 8$ 这 $8$ 个数字和一个 x 恰好不重不漏地分布在这 $3 \times 3$ 的网格中。

例如：

1 2 3
x 4 6
7 5 8

在游戏过程中，可以把 x 与其上、下、左、右四个方向之一的数字交换（如果存在）。

我们的目的是通过交换，使得网格变为如下排列（称为正确排列）：

1 2 3
4 5 6
7 8 x

例如，示例中图形就可以通过让 x 先后与右、下、右三个方向的数字交换成功得到正确排列。

交换过程如下：

1 2 3   1 2 3   1 2 3   1 2 3
x 4 6   4 x 6   4 5 6   4 5 6
7 5 8   7 5 8   7 x 8   7 8 x

现在，给你一个初始网格，请你求出得到正确排列至少需要进行多少次交换。

输入格式

输入占一行，将 $3 \times 3$ 的初始网格描绘出来。

例如，如果初始网格如下所示：

1 2 3 
x 4 6 
7 5 8 

则输入为：1 2 3 x 4 6 7 5 8

输出格式

输出占一行，包含一个整数，表示最少交换次数。

如果不存在解决方案，则输出 $-1$。

输入样例：

2 3 4 1 5 x 7 6 8

输出样例

19

解题

方法一：BFS

思路

求「最少能从初始状态到达结束状态的步数」问题的 BFS 模板。

代码

#include <iostream>
#include <queue>
#include <unordered_map>
#include <algorithm>

using namespace std;

const int DIRS[][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
string origin, target = "12345678x";

typedef pair<int, int> PII;

void bfs() {
    queue<string> que;
    unordered_map<string, PII> mp;
    que.push(origin);
    mp[origin] = {0, origin.find('x')};
    while (!que.empty()) {
        string state = que.front();
        que.pop();
        int step = mp[state].first;
        if (state == target) {
            printf("%d\n", step);
            return;
        }
        int pos = mp[state].second;
        int x = pos / 3, y = pos % 3;
        for (auto DIR : DIRS) {
            int nx = x + DIR[0], ny = y + DIR[1];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                swap(state[nx * 3 + ny], state[pos]);
                if (mp.find(state) == mp.end()) {
                    que.push(state);
                    mp[state] = {step + 1, nx * 3 + ny};
                }
                swap(state[nx * 3 + ny], state[pos]);
            }
        }
    }
    puts("-1");
}

int main() {
    for (int i = 0; i < 9; ++i) {
        char ch;
        scanf("%c ", &ch);
        origin += ch;
    }
    bfs();
    
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    static class State {
        char[] fg;
        int pos, step;
        
        public State(char[] fg, int pos, int step) {
            this.fg = fg;
            this.pos = pos;
            this.step = step;
        }
        
        @Override
        public boolean equals(Object obj) {
            State state = (State) obj;
            for (int i = 0; i < 9; ++i) {
                if (this.fg[i] != state.fg[i]) return false;
            }
            return true;
        }
        
        @Override
        public int hashCode() {
            return Arrays.hashCode(this.fg);
        }
        
        public State swap(int x) {
            char[] newFg = Arrays.copyOf(fg, 9);
            newFg[pos] = newFg[x];
            newFg[x] = 'x';
            return new State(newFg, x, step + 1);
        }
    }
    static State origin, target;
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] line = in.readLine().split("\\s+");
        int pos = 0;
        char[] fg = new char[9];
        for (int i = 0; i < 9; ++i) {
            fg[i] = line[i].charAt(0);
            if (line[i].charAt(0) == 'x') pos = i;
        }
        origin = new State(fg, pos, 0);
        target = new State(new char[]{'1', '2', '3', '4', '5', '6', '7', '8', 'x'}, 8, 0);
        bfs();
    }
    
    static void bfs() {
        Queue<State> que = new LinkedList<>();
        Set<State> vis = new HashSet<>();
        que.offer(origin);
        vis.add(origin);
        while (!que.isEmpty()) {
            State state = que.poll();
            if (state.equals(target)) {
                System.out.println(state.step);
                return;
            }
            int curr = state.pos;
            int x = curr / 3, y = curr % 3;
            for (int[] DIR : DIRS) {
                int nx = x + DIR[0], ny = y + DIR[1];
                if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                    State newState = state.swap(nx * 3 + ny);
                    if (vis.contains(newState)) continue;
                    que.offer(newState);
                    vis.add(newState);
                }
            }
        }
        System.out.println(-1);
    }
}