java拼图游戏BFS

### Java 实现拼图游戏 BFS 算法

#### 示例代码解释

为了实现拼图游戏中的广度优先搜索（BFS）算法，通常会遇到一些挑战，比如如何将问题转化为标准的BFS形式以及怎样高效地管理状态。下面是一个基于Java的简单示例，展示了如何利用字符串表示当前的游戏板面，并通过队列来进行层次遍历。

import java.util.*;

public class PuzzleSolver {
    private static final int[][] directions = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
    
    public String bfs(String start, String target) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        
        queue.offer(start);
        visited.add(start);

        Map<String, Integer> stepsMap = new HashMap<>();
        stepsMap.put(start, 0);

        while (!queue.isEmpty()) {
            String currentBoard = queue.poll();
            
            if (currentBoard.equals(target)) {
                return "Solution found in " + stepsMap.get(currentBoard) + " moves";
            }

            List<String> nextBoards = getNextStates(currentBoard);
            for (String nextState : nextBoards) {
                if (!visited.contains(nextState)) {
                    visited.add(nextState);
                    queue.offer(nextState);
                    stepsMap.put(nextState, stepsMap.get(currentBoard) + 1);
                }
            }
        }
        return "Unsolvable!";
    }

    private List<String> getNextStates(String board) {
        char[] chars = board.toCharArray();
        int zeroIndex = board.indexOf('0');
        int row = zeroIndex / 3;
        int col = zeroIndex % 3;

        List<String> result = new ArrayList<>();

        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];

            if (newRow >= 0 && newRow < 3 && newCol >= 0 && newCol < 3) {
                swap(chars, zeroIndex, newRow * 3 + newCol);
                result.add(new String(chars));
                swap(chars, zeroIndex, newRow * 3 + newCol); // Swap back to original state.
            }
        }
        return result;
    }

    private void swap(char[] array, int i, int j) {
        char temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
}

这段代码定义了一个`PuzzleSolver`类，其中包含了执行BFS所需的方法。这里的关键在于使用了字符串来存储每一步的状态变化，而不是直接操作二维数组，这样可以更方便地进行哈希表查重和队列操作[^4]。