本教程深入探讨如何高效解决“瓷砖铺设”这类网格优化问题。针对递归深度优先搜索在寻找最短路径时的性能瓶颈，文章详细阐述了采用广度优先搜索（bfs）来确保找到最优解的优势。同时，强调了通过将网格数据从字符串二维数组优化为一维字节数组、实现高效的状态管理以及在搜索前进行可行性预判，来显著提升算法处理大规模问题的能力。
1. 问题描述与初始方案分析
“瓷砖铺设”问题要求通过最少次数的相邻瓷砖交换，使得一个N x M的瓷砖地板上任意两个相邻瓷砖的颜色均不相同。输入为一个由R、G、B、C、P、Y六种颜色字符组成的网格，最大尺寸可达15x15。程序需要输出最小交换次数，若无解则输出“not possible”。
初始的解决方案通常采用递归的深度优先搜索（DFS）策略。这种方法通过不断尝试交换相邻瓷砖来探索所有可能的布局，并在找到一个符合条件的布局时记录交换次数。然而，这种递归方法存在显著的性能问题：
- 深度优先的局限性： DFS会沿着一条路径深入探索，即使这条路径很长，也无法保证找到的第一个解是最短的。为了找到最短路径，必须探索所有路径，这导致了大量的冗余计算。
- 状态重复探索： 在搜索过程中，算法可能会多次访问相同的瓷砖布局状态，但由于缺乏有效的状态记忆机制，会重复进行相同的计算。
- 数据表示效率低下： 使用 String[][] 存储网格状态，每次状态复制（如 cloneTiles 方法）和比较都涉及字符串操作，开销较大。
对于15x15的网格，状态空间极其庞大，上述问题会导致算法的执行时间呈指数级增长，使得即使是4x4的网格也可能耗费大量时间。
2. 算法优化：采用广度优先搜索（BFS）
对于需要寻找最短路径的问题，广度优先搜索（BFS）是比DFS更合适的选择。BFS从起始状态开始，逐层探索所有可达状态，保证了第一次到达目标状态的路径一定是最短的。
BFS的工作原理：
- 将初始状态加入队列，并标记为已访问。
- 从队列中取出一个状态，检查其是否为目标状态。
- 如果不是目标状态，生成所有通过一次相邻交换可达的新状态。
- 对于每个新状态：
- 如果该状态未被访问过，将其标记为已访问，并加入队列，同时记录到达该状态所需的交换次数（即父状态的交换次数加一）。
- 重复步骤2-4，直到队列为空或找到目标状态。
通过BFS，一旦找到符合条件的瓷砖布局，即可立即确定其为最小交换次数的解决方案。
3. 数据结构优化：提升状态处理效率
原始方案使用 String[][] 存储网格状态，这在内存和性能方面都存在瓶颈。优化数据表示是提高算法效率的关键一步。
3.1 颜色编码与一维数组表示
由于只有6种颜色，我们可以将每种颜色映射到一个字节（byte）或整数（int）值，例如：R=0, G=1, B=2, C=3, P=4, Y=5。
将二维网格转换为一维数组存储，可以显著减少内存开销并提高数据访问的局部性。对于一个 rows x cols 的网格，位置 (r, c) 处的元素可以映射到一维数组的 r * cols + c 索引。
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class TileGridOptimizer {
// 颜色字符到字节值的映射
private static final Map COLOR_TO_BYTE_MAP = new HashMap<>();
static {
COLOR_TO_BYTE_MAP.put("R", (byte) 0);
COLOR_TO_BYTE_MAP.put("G", (byte) 1);
COLOR_TO_BYTE_MAP.put("B", (byte) 2);
COLOR_TO_BYTE_MAP.put("C", (byte) 3);
COLOR_TO_BYTE_MAP.put("P", (byte) 4);
COLOR_TO_BYTE_MAP.put("Y", (byte) 5);
}
/**
* 将二维字符串网格转换为一维字节数组表示。
*
* @param tiles 原始的二维字符串网格
* @return 转换后的一维字节数组
*/
public static byte[] convertToByteArray(String[][] tiles) {
int rows = tiles.length;
int cols = tiles[0].length;
byte[] byteArray = new byte[rows * cols];
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
byteArray[r * cols + c] = COLOR_TO_BYTE_MAP.get(tiles[r][c]);
}
}
return byteArray;
}
/**
* 在一维字节数组中检查指定位置的瓷砖是否与其相邻瓷砖颜色相同。
*
* @param grid 一维字节数组表示的网格
* @param rows 网格行数
* @param cols 网格列数
* @param r 待检查瓷砖的行索引
* @param c 待检查瓷砖的列索引
* @return 如果存在相邻瓷砖颜色相同，则返回 true；否则返回 false。
*/
public static boolean hasAdjacentSameColor(byte[] grid, int rows, int cols, int r, int c) {
byte currentColor = grid[r * cols + c];
// 检查右侧
if (c + 1 < cols && grid[r * cols + (c + 1)] == currentColor) return true;
// 检查左侧
if (c - 1 >= 0 && grid[r * cols + (c - 1)] == currentColor) return true;
// 检查下方
if (r + 1 < rows && grid[(r + 1) * cols + c] == currentColor) return true;
// 检查上方
if (r - 1 >= 0 && grid[(r - 1) * cols + c] == currentColor) return true;
return false;
}
} 3.2 优势：
- 内存效率： byte 类型占用空间小，远小于 String 对象。
- 复制速度： byte[] 的复制操作（如 System.arraycopy() 或 clone()）远快于 String[][] 的深拷贝。
- 缓存局部性： 一维数组在内存中是连续存储的，有利于CPU缓存命中，提升访问速度。
4. 状态管理与剪枝优化
为了避免重复计算和无限循环，有效管理已访问状态至关重要。
4.1 已访问状态集合
使用 java.util.HashSet 来存储所有已探索过的网格状态。当生成新的状态时，先检查它是否已存在于 HashSet 中。
4.2 状态ID的生成
对于 byte[] 数组，直接将其作为 HashSet 的键是不可行的，因为 HashSet 默认使用对象引用进行比较。需要一个能够代表数组内容的唯一ID。
-
方案一：转换为字符串 将 byte[] 转换为一个紧凑的字符串。
// 示例：将 byte[] 转换为字符串作为状态ID public static String getGridId(byte[] grid) { StringBuilder sb = new StringBuilder(grid.length); for (byte b : grid) { sb.append(b); // 或者 sb.append((char)('0' + b)); 确保字符是可打印的 } return sb.toString(); } // 在BFS中： // SetvisitedStates = new HashSet<>(); // String currentId = getGridId(currentGrid); // if (visitedStates.contains(currentId)) continue; // visitedStates.add(currentId); 这种方法简单，但字符串的创建和比较仍有一定开销。
-
方案二：自定义包装类 创建一个包装类来封装 byte[]，并重写 hashCode() 和 equals() 方法，使其基于数组内容进行比较。
import java.util.Arrays; import java.util.Objects; // For Objects.hash public class ByteArrayWrapper { private final byte[] array; public ByteArrayWrapper(byte[] array) { this.array = array; } public byte[] getArray() { return array; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; ByteArrayWrapper that = (ByteArrayWrapper) o; return Arrays.equals(array, that.array); } @Override public int hashCode() { return Arrays.hashCode(array); } } // 在BFS中： // SetvisitedStates = new HashSet<>(); // ByteArrayWrapper currentWrapper = new ByteArrayWrapper(currentGrid); // if (visitedStates.contains(currentWrapper)) continue; // visitedStates.add(currentWrapper); 这是推荐的方法，因为它直接利用了 Arrays.equals() 和 Arrays.hashCode() 的高效实现。
4.3 可行性预判（剪枝）
在搜索开始之前进行预检查，可以快速排除无解的情况，避免不必要的计算。例如，如果某种颜色的瓷砖数量过多，以至于无法在不相邻的情况下放置，则可以直接判断为“not possible”。
以问题描述中的示例 GGYGP CGGRG 为例，一个2x5的网格共有10个瓷砖位。如果其中有6个'G'，即使最优布局也无法避免两个'G'相邻，因为最多只能放置5个不相邻的'G'。
// 简单的可行性预判示例
public static boolean isPotentiallySolvable(String[][] initialTiles) {
int rows = initialTiles.length;
int cols = initialTiles[0].length;
Map colorCounts = new HashMap<>();
for (String[] row : initialTiles) {
for (String tile : row) {
colorCounts.put(tile, colorCounts.getOrDefault(tile, 0) + 1);
}
}
// 粗略检查：如果某种颜色瓷砖数量超过总瓷砖数的一半（向上取整），
// 那么在棋盘格布局下，可能无法避免相邻。
// 更精确的检查需要考虑棋盘格染色法，但这是一个简单有效的初步判断。
for (int count : colorCounts.values()) {
if (count > (rows * cols + 1) / 2) { // 适用于棋盘格布局的粗略上限
return false; // 数量过多，可能无法解决
}
}
return true;
} 这个预判只是一个启发式方法，更精确的判断需要考虑网格的连通性等复杂因素。
5. BFS算法骨架示例
结合上述优化，一个高效的BFS算法骨架如下：
import java.util.*;
public class TileSolverBFS {
// ... (COLOR_TO_BYTE_MAP, convertToByteArray, hasAdjacentSameColor, ByteArrayWrapper 等辅助方法) ...
/**
* 定义一个状态类，包含当前网格布局和达到该布局所需的交换次数
*/
static class State {
byte[] grid;
int moves;
int rows;
int cols;
public State(byte[] grid, int moves, int rows, int cols) {
this.grid = grid;
this.moves = moves; 
