优化瓷砖排列算法：提升效率与寻找最短路径

import java.util.*;

// 假设有一个TileBoard类来表示棋盘状态，并实现equals和hashCode方法
class TileBoard {
    byte[] tiles; // 优化后的棋盘表示
    int rows;
    int cols;

    public TileBoard(byte[] tiles, int rows, int cols) {
        this.tiles = tiles;
        this.rows = rows;
        this.cols = cols;
    }

    // 检查当前棋盘是否已解决（无相邻同色瓷砖）
    public boolean isSolved() {
        // 实现逻辑：遍历所有瓷砖，检查相邻颜色
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (hasAdjacentSameColor(r, c)) {
                    return false;
                }
            }
        }
        return true;
    }

    // 检查指定位置的瓷砖是否有相邻同色瓷砖
    private boolean hasAdjacentSameColor(int r, int c) {
        byte currentColor = tiles[r * cols + c];
        // 检查右侧
        if (c + 1 < cols && tiles[r * cols + (c + 1)] == currentColor) return true;
        // 检查左侧
        if (c - 1 >= 0 && tiles[r * cols + (c - 1)] == currentColor) return true;
        // 检查下方
        if (r + 1 < rows && tiles[(r + 1) * cols + c] == currentColor) return true;
        // 检查上方
        if (r - 1 >= 0 && tiles[(r - 1) * cols + c] == currentColor) return true;
        return false;
    }

    // 生成所有可能的相邻交换后的新棋盘状态
    public List<TileBoard> generateNextStates() {
        List<TileBoard> nextStates = new ArrayList<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                // 尝试与右侧交换
                if (c + 1 < cols) {
                    nextStates.add(swap(r, c, r, c + 1));
                }
                // 尝试与下方交换
                if (r + 1 < rows) {
                    nextStates.add(swap(r, c, r + 1, c));
                }
                // 注意：只需考虑向右和向下交换，因为反向交换会在其他瓷砖位置考虑
                // 避免生成重复的交换操作，例如 (r,c) 与 (r,c+1) 交换，和 (r,c+1) 与 (r,c) 交换是等价的
            }
        }
        return nextStates;
    }

    // 执行一次交换并返回新的TileBoard对象
    private TileBoard swap(int r1, int c1, int r2, int c2) {
        byte[] newTiles = Arrays.copyOf(this.tiles, this.tiles.length); // 浅拷贝1D数组
        byte temp = newTiles[r1 * cols + c1];
        newTiles[r1 * cols + c1] = newTiles[r2 * cols + c2];
        newTiles[r2 * cols + c2] = temp;
        return new TileBoard(newTiles, rows, cols);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TileBoard tileBoard = (TileBoard) o;
        return Arrays.equals(tiles, tileBoard.tiles);
    }

    @Override
    public int hashCode() {
        return Arrays.hashCode(tiles);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < tiles.length; i++) {
            sb.append(tiles[i]);
            if ((i + 1) % cols == 0) sb.append("\n");
        }
        return sb.toString();
    }
}

// 状态类，用于BFS队列
class BFSState {
    TileBoard board;
    int moves;

    public BFSState(TileBoard board, int moves) {
        this.board = board;
        this.moves = moves;
    }
}

public class TileSolverBFS {

    public static int solve(TileBoard initialBoard) {
        Queue<BFSState> queue = new LinkedList<>();
        Set<TileBoard> visitedBoards = new HashSet<>(); // 使用TileBoard作为key，因为其equals和hashCode已定义

        // 初始状态
        BFSState initialState = new BFSState(initialBoard, 0);
        queue.offer(initialState);
        visitedBoards.add(initialBoard);

        while (!queue.isEmpty()) {
            BFSState current = queue.poll();

            // 如果当前棋盘已解决，则找到最短路径
            if (current.board.isSolved()) {
                return current.moves;
            }

            // 生成所有可能的下一步状态
            for (TileBoard nextBoard : current.board.generateNextStates()) {
                if (!visitedBoards.contains(nextBoard)) {
                    visitedBoards.add(nextBoard);
                    queue.offer(new BFSState(nextBoard, current.moves + 1));
                }
            }
        }

        return -1; // 如果队列为空仍未找到解，则无解
    }

    public static void main(String[] args) {
        // 示例输入: RGR RPC GRB YPG (3x4)
        // 映射颜色到字节：R=0, G=1, B=2, C=3, P=4, Y=5
        byte[] initialTilesData = {
            0, 1, 0, // RGR
            0, 4, 3, // RPC
            1, 0, 2, // GRB
            5, 4, 1  // YPG (这里原问题描述是3x4，但示例是4行3列。根据示例RGR GPC RBR YPG，我理解是3x4)
                     // 假设是3行4列：RGRR, GPC_, RBR_, YPG_
                     // 示例输入RGR RPC GRB YPG 是4行3列
                     // R G R
                     // R P C
                     // G R B
                     // Y P G
        };
        // 实际根据问题描述是 3行4列 RGR RPC GRB YPG
        // R G R _
        // R P C _
        // G R B _
        // Y P G _
        // 重新理解示例输入：RGR RPC GRB YPG 是指4行3列
        // R G R
        // R P C
        // G R B
        // Y P G
        // 那么初始数据应该是 4行3列
        byte[] exampleTiles = {
            0, 1, 0, // R G R
            0, 4, 3, // R P C
            1, 0, 2, // G R B
            5, 4, 1  // Y P G
        };
        int rows = 4;
        int cols = 3;

        TileBoard initialBoard = new TileBoard(exampleTiles, rows, cols);
        System.out.println("初始棋盘:\n" + initialBoard);
        int minSwaps = solve(initialBoard);

        if (minSwaps != -1) {
            System.out.println("最小交换次数: " + minSwaps); // 预期输出 2
        } else {
            System.out.println("无解");
        }

        // 示例：不可能修复的情况 GGYGP CGGRG (2x5)
        // G G Y G P
        // C G G R G
        byte[] impossibleTiles = {
            1, 1, 5, 1, 4, // G G Y G P
            3, 1, 1, 0, 1  // C G G R G
        };
        rows = 2;
        cols = 5;
        TileBoard impossibleBoard = new TileBoard(impossibleTiles, rows, cols);
        System.out.println("\n不可能修复的棋盘:\n" + impossibleBoard);
        minSwaps = solve(impossibleBoard);
        if (minSwaps != -1) {
            System.out.println("最小交换次数: " + minSwaps);
        } else {
            System.out.println("无解"); // 预期输出 "无解"
        }
    }

    // 辅助方法：将字符颜色转换为字节
    public static byte colorToByte(char c) {
        switch (c) {
            case 'R': return 0;
            case 'G': return 1;
            case 'B': return 2;
            case 'C': return 3;
            case 'P': return 4;
            case 'Y': return 5;
            default: throw new IllegalArgumentException("未知颜色: " + c);
        }
    }
}