本文针对一个经典的瓷砖铺设问题，探讨如何优化算法以在有限的步数内，使相邻瓷砖颜色不同。初始的深度优先搜索（dfs）方法因其指数级复杂度和低效的数据结构而难以处理大规模问题。我们将详细介绍如何通过改用广度优先搜索（bfs）来确保找到最优解，并结合高效的棋盘状态表示（如扁平化字节数组）和哈希集合来有效管理已访问状态，从而显著提升算法性能。
1. 问题定义：不相邻同色瓷砖铺设
假设我们有一个 M x N 的瓷砖地板，其中每块瓷砖都有六种预设颜色之一（红R、绿G、蓝B、青C、紫P、黄Y）。初始状态下，地板可能存在相邻瓷砖颜色相同的情况。我们的目标是通过最少次数的相邻瓷砖交换操作，使地板达到一个合规状态：即任意两块相邻（水平或垂直）的瓷砖颜色都不同。输入是一个表示地板初始布局的字符矩阵，输出是达到合规状态所需的最小交换次数。如果无法达到合规状态，则输出“not possible”。问题的规模最大为15x15的瓷砖地板。
示例输入:
RGR RPC GRB YPG
这是一个3x4的地板，目标是找到最小交换次数。
2. 初始解决方案及其局限性
提供的初始解决方案采用了一种递归的深度优先搜索（DFS）策略来探索所有可能的瓷砖交换路径。其核心思想是：
- 检查当前棋盘是否已解决。
- 如果未解决且当前交换次数小于已知的最小次数，则尝试在所有存在相邻同色瓷砖的位置进行四向（上、下、左、右）交换。
- 每次交换后，递归调用自身，并增加交换计数。
然而，这种方法存在以下几个关键的效率问题：
- 搜索策略低效： DFS会深入探索某一条路径，即使这条路径不是最短的。在找到一个解决方案后，它仍然需要回溯并探索其他所有路径，才能确定找到的是否为最优解。对于寻找最小步数的问题，DFS并非最佳选择。
-
状态重复计算： 算法使用 ArrayList
tilesIDs 来存储已访问的棋盘状态ID，以避免重复计算。但是，linearSearch 在 ArrayList 中查找字符串ID的效率是线性的（O(N)），当已访问状态数量庞大时，会显著降低性能。 - 数据结构低效： 棋盘状态 String[][] tiles 使用字符串数组表示，每次复制棋盘（cloneTiles 方法）都会创建大量的 String 对象和数组，导致内存开销大且复制操作缓慢。
- 异常处理滥用： 使用 try-catch 块来处理边界条件（例如，尝试访问 tiles[i][l-1] 时越界）虽然功能上可行，但频繁的异常抛出和捕获会带来额外的性能开销，不如直接进行边界检查。
这些因素共同导致了算法的指数级时间复杂度，使其在处理4x4以上规模的棋盘时变得极其缓慢。
3. 优化搜索算法：广度优先搜索 (BFS)
对于寻找从起始状态到目标状态的最小步数问题，广度优先搜索（BFS）是理想的选择。BFS从起始状态开始，逐层探索所有可能的下一步状态。由于它总是先探索距离起始状态更近的节点，因此一旦找到目标状态，它所经历的路径必然是最短的。
BFS实现要点：
- 队列 (Queue)： 用于存储待访问的棋盘状态及其对应的交换次数。
- 访问集合 (Visited Set)： 用于存储所有已访问过的棋盘状态的唯一标识，以避免重复探索。使用 HashSet 可以提供接近 O(1) 的查找效率。
- 状态表示： 队列中存储的每个元素应包含当前棋盘状态和达到该状态所需的交换次数。
BFS伪代码示例：
// 定义一个类来封装棋盘状态和交换次数
class State {
byte[] board; // 扁平化棋盘表示
int moves; // 达到此状态的交换次数
// 构造函数、equals和hashCode方法
// ...
}
public int solveTiledFloor(byte[] initialBoard) {
Queue queue = new LinkedList<>();
HashSet visited = new HashSet<>(); // 存储棋盘ID字符串
// 初始状态入队
State initialState = new State(initialBoard, 0);
queue.offer(initialState);
visited.add(computeID(initialBoard)); // 将初始状态的ID加入已访问集合
while (!queue.isEmpty()) {
State current = queue.poll();
// 检查当前状态是否已解决
if (isSolved(current.board)) {
return current.moves; // 找到第一个解决方案，即为最短路径
}
// 遍历所有可能的相邻交换
for (int i = 0; i < R; i++) {
for (int l = 0; l < C; l++) {
// 对于当前瓷砖 (i, l)，尝试与相邻瓷砖交换
// 考虑上、下、左、右四个方向的交换
// ...
// 假设与右侧瓷砖交换
if (l + 1 < C) {
byte[] nextBoard = cloneBoard(current.board);
// 执行交换操作
byte temp = nextBoard[i * C + l];
nextBoard[i * C + l] = nextBoard[i * C + l + 1];
nextBoard[i * C + l + 1] = temp;
String nextBoardID = computeID(nextBoard);
if (!visited.contains(nextBoardID)) {
visited.add(nextBoardID);
queue.offer(new State(nextBoard, current.moves + 1));
}
}
// 对其他方向（左、上、下）进行类似处理
// ...
}
}
}
return -1; // 表示无解
} 4. 优化数据表示与状态管理
原始解决方案中使用 String[][] 来表示棋盘，并用 String 来作为状态ID。这在内存和性能方面都效率低下。
4.1 扁平化数组表示
建议将 String[][] 替换为一维的 byte[] 或 char[] 数组。
- 颜色映射： 将六种颜色（R, G, B, C, P, Y）映射为小的整数值（例如，0到5）。这样，每个瓷砖的颜色就可以用一个 byte 来存储。
- 一维数组： 一个 M x N 的棋盘可以表示为一个长度为 M * N 的一维数组。例如，tiles[i][l] 对应于一维数组中的 board[i * N + l]。
-
优势：
- 内存效率： byte 类型占用空间小，减少整体内存消耗。
- 复制速度： 一维数组的复制操作通常比二维数组更快，尤其是使用 System.arraycopy() 或 clone() 方法。
- 内存局部性： 数据在内存中连续存储，有利于CPU缓存。
4.2 高效的状态ID生成与管理
- 状态ID： 对于 byte[] 数组，可以直接使用 Arrays.toString(byte[]) 作为状态ID字符串，或者更高效地，实现一个自定义的哈希函数。最简单且通常足够有效的方法是直接将 byte[] 转换为 String。
-
HashSet for Visited States： 使用 HashSet
来存储已访问状态的ID，提供平均 O(1) 的查找、添加和删除效率，远优于 ArrayList 的线性搜索。
示例：棋盘与ID转换
// 假设 R=0, G=1, B=2, C=3, P=4, Y=5
// 棋盘大小 R行 C列
private static int R, C;
// 将二维坐标 (row, col) 转换为一维索引
private int to1D(int row, int col) {
return row * C + col;
}
// 检查相邻瓷砖
public boolean adjacentPresent(byte[] board, byte color, int row, int col) {
int idx = to1D(row, col);
// 检查右侧
if (col + 1 < C && board[to1D(row, col + 1)] == color) return true;
// 检查左侧
if (col - 1 >= 0 && board[to1D(row, col - 1)] == color) return true;
// 检查下方
if (row + 1 < R && board[to1D(row + 1, col)] == color) return true;
// 检查上方
if (row - 1 >= 0 && board[to1D(row - 1, col)] == color) return true;
return false;
}
// 克隆棋盘（一维字节数组）
public byte[] cloneBoard(byte[] original) {
return original.clone(); // byte[] 的 clone() 是深拷贝
}
// 计算棋盘ID (用于HashSet)
public String computeID(byte[] board) {
// 将字节数组转换为字符串作为唯一标识
// Arrays.toString(byte[]) 会生成 [0, 1, 2, ...] 形式的字符串
// 或者可以自定义更紧凑的编码方式
return Arrays.toString(board);
}5. 处理无解情况
在BFS中，如果队列变空（queue.isEmpty() 为 true），这意味着从起始状态无法到达任何目标状态，即无解。此时可以返回一个特殊值（例如 -1）表示“not possible”。
另外，在某些情况下，即使理论上存在足够数量的瓷砖，也可能因为颜色分布不均而无法构成合规布局。例如，如果一个2x2的棋盘需要4种不同颜色的瓷砖，但只提供了3种颜色，那么无论如何交换都无法满足条件。更复杂的情况是，如果某种颜色在棋盘中出现的次数过多，以至于无法避免相邻同色，例如一个5个格子组成的棋盘，其中有3个G，而G最多只能出现2次不相邻。对于这些情况，可以在算法开始前进行一些预检查，例如统计每种颜色的数量，并与棋盘大小进行比较，判断是否存在明显的无解情况。
6. 总结与注意事项
通过将搜索策略从低效的DFS（回溯）改为BFS，并结合优化的数据结构（扁平化字节数组）和高效的状态管理（哈希集合），我们可以显著提升解决“Tiled Floor”问题的算法效率。
关键优化点回顾：
- 算法： 从DFS转向BFS，确保找到的是最短路径。
- 数据结构： 将 String[][] 替换为 byte[]，将颜色映射为整数，以提高内存效率和复制速度。
- 状态管理： 使用 HashSet 存储已访问状态的ID，避免重复计算，并提供快速查找。
- 边界检查： 避免使用 try-catch 进行边界检查，直接通过条件判断来处理，提高运行时效率。
尽管BFS能找到最短路径，但对于非常大的棋盘和深度很深的解，状态空间仍然可能非常庞大。15x15的棋盘有225个瓷砖，即使每个瓷砖只有6种颜色，状态数量依然惊人。因此，在实际应用中，如果BFS仍无法满足性能要求，可能需要考虑更高级的启发式搜索算法，如A*搜索，它结合了BFS的完备性和启发式函数的效率，但实现复杂度会更高。
