题目描述

在一个3×3的网格中,1~8这8个数字和一个“x”恰好不重不漏地分布在这3×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×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 + map双向bfsA* ....都能解决这道题。

但是由于我比较菜,所以暂时先贴 朴素bfs + map 的解法。

其实这题也不难,麻烦的主要就是两个点:

  • 1、如何记录状态
  • 2、如何记录当前变换到当前状态所需的最少交换次数

只要解决这两个问题,那这题其实就很简单了。

因为状态是一个个的3 x 3的矩阵,不太好存,所以我们能不能想到一个比较好存的方式来表示每个3 x 3的矩阵。动动脑袋瓜子想想= ̄ω ̄=。

我们可以把每个3 x 3的矩阵转化为一个字符串序列,比如:

1 2 3
x 4 6
7 5 8

我们可以把它转为123x46758,这样的话,我们状态表示就很轻松了。

那么还剩下一个问题,变换到当前状态的最小交换次数应该怎么存呢?

其实这里开个哈希表(C++对应unordered_map,java对应HashMap,python对应字典)就可以了。

既然现在两个问题都解决了,那么代码就很好写了= ̄ω ̄=

朴素版bfs + map

C++ 实现
#include <iostream>
#include <cstring>
#include <queue>
#include <unordered_map>
using namespace std;
unordered_map<string, int> dist;

int bfs(string start)
{
    string end = "12345678x";
    int dir[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
    
    queue<string> q;
    dist[start] = 0;
    q.push(start);
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
        
        if (t == end) return dist[t];
        
        int distance = dist[t];
        
        // 向四个方向扩展
        for (int i = 0; i < 4; i ++ )
        {
            int cur = t.find('x');
            // 获得 x 在 3 x 3 矩阵中的对应下标
            int x = cur / 3, y = cur % 3;
            int a = x + dir[i][0], b = y + dir[i][1];
            if (a >= 0 && a < 3 && b >= 0 && b < 3)
            {
                // 交换对应位置的字符
                swap(t[cur], t[a * 3 + b]);
                if (!dist.count(t))
                {
                    dist[t] = distance + 1;
                    q.push(t);
                }
                // 记得复原!!!
                swap(t[cur], t[a * 3 + b]);
            }
        }
    }
    
    return -1;
}

int main()
{
    string start;
    for (int i = 0; i < 9; i ++ )
    {
        char s;
        cin >> s;
        start += s;
    }
    
    cout << bfs(start) << endl;
    
    return 0;
}
Java实现
package cn.lwjppz.solution;

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

/**
 * @author : lwj
 * @since : 2021-02-08
 */
public class EightDigital {

    static class Solution {
        /**
         * 标记状态是否访问过及到达此状态所需最短步数
         */
        private Map<String, Integer> hash = new HashMap<>(1 << 3);

        /**
         * 方向数组
         */
        private final int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

        /**
         * 初始状态
         */
        private final String start;

        public Solution(String start) {
            this.start = start;
        }

        public String swap(String str, int source, int target) {
            StringBuilder sb = new StringBuilder(str);
            char ch = sb.charAt(source);
            sb.replace(source, source + 1, String.valueOf(sb.charAt(target)));
            sb.replace(target, target + 1, String.valueOf(ch));
            return sb.toString();
        }

        public int bfs() {
            Queue<String> q = new LinkedList<>();
            q.offer(start);
            hash.put(start, 0);
            String end = "12345678x";
            while (!q.isEmpty()) {
                String t = q.poll();
                if (end.compareTo(t) == 0) {
                    break;
                }
                for (int i = 0; i < 4; i++) {
                    int index = t.indexOf('x');
                    int x = index / 3 + dir[i][0], y = index % 3 + dir[i][1];
                    if (x >= 0 && x < 3 && y >= 0 && y < 3) {
                        int cur = x * 3 + y;
                        String curState = swap(t, index, cur);
                        if (hash.getOrDefault(curState, 0) == 0) {
                            hash.put(curState, hash.get(t) + 1);
                            q.offer(curState);
                        }
                    }
                }
            }
            return hash.getOrDefault(end, -1);
        }
    }

    static class Reader {
        static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer tokenizer = new StringTokenizer("");

        static String nextLine() throws IOException {
            return reader.readLine();
        }

        static String next() throws IOException {
            while (!tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(reader.readLine());
            }
            return tokenizer.nextToken();
        }

        static int nextInt() throws IOException {
            return Integer.parseInt(next());
        }

        static double nextDouble() throws IOException {
            return Double.parseDouble(next());
        }

        static void close() throws IOException {
            reader.close();
        }
    }

    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(new PrintStream(System.out));
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            sb.append(Reader.next());
        }

        Solution solution = new Solution(sb.toString());

        int step = solution.bfs();
        out.println(step);

        out.flush();
    }
}

题目链接:https://www.luogu.com.cn/problem/P1379,这题更简化

Q.E.D.