优化瓷砖排列算法：从暴力搜索到高效解决方案

// 假设 TileState 类包含 tiles (棋盘布局) 和 moves (交换次数)
// 假设 computeID(tiles) 生成一个唯一标识符
// 假设 isSolved(tiles) 检查棋盘是否满足条件
// 假设 generateNextStates(tiles) 生成所有可能的下一个棋盘布局及其对应的交换操作

public int solveTiledFloor(String[][] initialTiles) {
    Queue<TileState> queue = new LinkedList<>();
    Set<String> visitedStates = new HashSet<>(); // 存储棋盘布局的ID

    TileState initialState = new TileState(initialTiles, 0);
    queue.offer(initialState);
    visitedStates.add(computeID(initialTiles));

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

        if (isSolved(current.tiles)) {
            return current.moves; // 找到最优解
        }

        // 遍历所有可能的相邻瓷砖交换
        for (int r = 0; r < current.tiles.length; r++) {
            for (int c = 0; c < current.tiles[0].length; c++) {
                // 尝试与右侧交换
                if (c + 1 < current.tiles[0].length) {
                    String[][] nextTiles = cloneAndSwap(current.tiles, r, c, r, c + 1);
                    String nextID = computeID(nextTiles);
                    if (!visitedStates.contains(nextID)) {
                        visitedStates.add(nextID);
                        queue.offer(new TileState(nextTiles, current.moves + 1));
                    }
                }
                // 尝试与下方交换
                if (r + 1 < current.tiles.length) {
                    String[][] nextTiles = cloneAndSwap(current.tiles, r, c, r + 1, c);
                    String nextID = computeID(nextTiles);
                    if (!visitedStates.contains(nextID)) {
                        visitedStates.add(nextID);
                        queue.offer(new TileState(nextTiles, current.moves + 1));
                    }
                }
                // (同理可添加与左侧和上方交换的逻辑，但为避免重复生成，通常只考虑右/下交换)
            }
        }
    }
    return -1; // 表示无解
}

// 颜色到字节的映射
private static final Map<String, Byte> COLOR_TO_BYTE = new HashMap<>();
private static final String[] BYTE_TO_COLOR = {"R", "G", "B", "C", "P", "Y"};

static {
    COLOR_TO_BYTE.put("R", (byte) 0);
    COLOR_TO_BYTE.put("G", (byte) 1);
    COLOR_TO_BYTE.put("B", (byte) 2);
    COLOR_TO_BYTE.put("C", (byte) 3);
    COLOR_TO_BYTE.put("P", (byte) 4);
    COLOR_TO_BYTE.put("Y", (byte) 5);
}

// 棋盘尺寸
private static int NUM_ROWS;
private static int NUM_COLS;

// 将初始 String[][] 转换为 byte[]
public byte[] convertToByteArray(String[][] tiles) {
    NUM_ROWS = tiles.length;
    NUM_COLS = tiles[0].length;
    byte[] byteArray = new byte[NUM_ROWS * NUM_COLS];
    for (int r = 0; r < NUM_ROWS; r++) {
        for (int c = 0; c < NUM_COLS; c++) {
            byteArray[r * NUM_COLS + c] = COLOR_TO_BYTE.get(tiles[r][c]);
        }
    }
    return byteArray;
}

// 交换一维字节数组中的两个元素
public byte[] cloneAndSwap(byte[] currentTiles, int r1, int c1, int r2, int c2) {
    byte[] newTiles = currentTiles.clone(); // 浅拷贝，但对于基本类型数组是深拷贝
    int index1 = r1 * NUM_COLS + c1;
    int index2 = r2 * NUM_COLS + c2;
    byte temp = newTiles[index1];
    newTiles[index1] = newTiles[index2];
    newTiles[index2] = temp;
    return newTiles;
}

// 检查一维字节数组表示的棋盘是否满足条件
public boolean isSolved(byte[] tiles) {
    for (int r = 0; r < NUM_ROWS; r++) {
        for (int c = 0; c < NUM_COLS; c++) {
            byte currentColor = tiles[r * NUM_COLS + c];
            // 检查右侧
            if (c + 1 < NUM_COLS && tiles[r * NUM_COLS + (c + 1)] == currentColor) return false;
            // 检查下方
            if (r + 1 < NUM_ROWS && tiles[(r + 1) * NUM_COLS + c] == currentColor) return false;
        }
    }
    return true;
}

// 计算状态ID（用于 HashSet）
public String computeID(byte[] tiles) {
    return Arrays.toString(tiles); // 或者使用更紧凑的编码方式
}

public boolean canPossiblySolve(String[][] initialTiles) {
    int[] colorCounts = new int[6]; // R, G, B, C, P, Y 对应的计数
    int totalTiles = 0;
    for (String[] row : initialTiles) {
        for (String tile : row) {
            colorCounts[COLOR_TO_BYTE.get(tile)]++;
            totalTiles++;
        }
    }

    // 简单启发式：如果任何一种颜色数量超过总瓷砖数的一半，则可能无解
    // (这只是一个粗略的检查，并非所有无解情况都能通过此检测)
    for (int count : colorCounts) {
        if (count > Math.ceil(totalTiles / 2.0)) {
            // 对于一个棋盘，如果某种颜色瓷砖数量过多，可能无法避免相邻
            // 例如，一个2x2棋盘有4个G，则肯定无法解决
            // 更精确的判断需要考虑棋盘的二分图着色性质，但通常复杂
            return false; 
        }
    }
    return true;
}