已有最小替换次数计算代码，如何更新字符矩阵生成合法结果？

问题描述 #

给定由a-z小写英文字符组成的矩阵，需修改最少数量的字符，使得矩阵中每个字符的上下左右相邻字符均互不相同。目前已实现计算最小替换次数的Java代码，现需补充矩阵更新逻辑，输出一个符合要求的合法矩阵。

示例 #

输入矩阵 #

acaa
dddd
bbbb
ccce

合法输出矩阵示例 #

acac
dede
baba
cece

现有最小替换次数计算代码（中文注释版） #

public static int solve(char[][] matrix) {
    int rows = matrix.length, cols = matrix[0].length;
    // 上下左右四个方向的偏移量
    int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int replaceCount = 0;
    // 记录已经标记为需要修改的位置
    Set<String> modifiedPositions = new HashSet<>();

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            char currentChar = matrix[i][j];
            String currentKey = i + ":" + j;
            // 如果当前位置已被标记为修改过，跳过
            if (modifiedPositions.contains(currentKey)) {
                continue;
            }
            // 遍历四个相邻方向
            for (int k = 0; k < 4; k++) {
                int x = i + directions[k][0];
                int y = j + directions[k][1];
                String neighborKey = x + ":" + y;
                // 检查相邻位置是否在矩阵范围内且未被标记
                if (x >= 0 && y >= 0 && x < rows && y < cols && !modifiedPositions.contains(neighborKey)) {
                    // 如果相邻字符和当前字符相同，标记该相邻位置为需要修改，计数加1
                    if (matrix[x][y] == currentChar) {
                        replaceCount++;
                        modifiedPositions.add(neighborKey);
                    }
                }
            }
        }
    }
    return replaceCount;
}

合法矩阵生成实现代码 #

基于上述最小次数的标记逻辑，我们可以对标记为需要修改的位置，选择一个与已确定的相邻字符均不同的字符（优先选择a、b、c这类基础字符，确保最少修改且符合要求）：

import java.util.HashSet;
import java.util.Set;

public class MatrixProcessor {
    public static int solve(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        int replaceCount = 0;
        Set<String> modifiedPositions = new HashSet<>();

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char currentChar = matrix[i][j];
                String currentKey = i + ":" + j;
                if (modifiedPositions.contains(currentKey)) {
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    int x = i + directions[k][0];
                    int y = j + directions[k][1];
                    String neighborKey = x + ":" + y;
                    if (x >= 0 && y >= 0 && x < rows && y < cols && !modifiedPositions.contains(neighborKey)) {
                        if (matrix[x][y] == currentChar) {
                            replaceCount++;
                            modifiedPositions.add(neighborKey);
                        }
                    }
                }
            }
        }
        return replaceCount;
    }

    public static char[][] generateValidMatrix(char[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Set<String> modifiedPositions = new HashSet<>();
        // 复制原矩阵，避免修改原始输入
        char[][] resultMatrix = new char[rows][cols];
        for (int i = 0; i < rows; i++) {
            System.arraycopy(matrix[i], 0, resultMatrix[i], 0, cols);
        }

        // 第一步：标记需要修改的位置，逻辑与solve方法一致
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char currentChar = resultMatrix[i][j];
                String currentKey = i + ":" + j;
                if (modifiedPositions.contains(currentKey)) {
                    continue;
                }
                for (int k = 0; k < 4; k++) {
                    int x = i + directions[k][0];
                    int y = j + directions[k][1];
                    String neighborKey = x + ":" + y;
                    if (x >= 0 && y >= 0 && x < rows && y < cols && !modifiedPositions.contains(neighborKey)) {
                        if (resultMatrix[x][y] == currentChar) {
                            modifiedPositions.add(neighborKey);
                        }
                    }
                }
            }
        }

        // 第二步：对标记位置进行替换，选择与相邻字符不同的最小字母
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                String currentKey = i + ":" + j;
                if (modifiedPositions.contains(currentKey)) {
                    Set<Character> neighborChars = new HashSet<>();
                    // 收集所有相邻已确定的字符
                    for (int k = 0; k < 4; k++) {
                        int x = i + directions[k][0];
                        int y = j + directions[k][1];
                        if (x >= 0 && y >= 0 && x < rows && y < cols) {
                            neighborChars.add(resultMatrix[x][y]);
                        }
                    }
                    // 从a开始找第一个不在相邻字符中的字母
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (!neighborChars.contains(c)) {
                            resultMatrix[i][j] = c;
                            break;
                        }
                    }
                }
            }
        }

        return resultMatrix;
    }

    // 测试用例
    public static void main(String[] args) {
        char[][] input = {
                {'a','c','a','a'},
                {'d','d','d','d'},
                {'b','b','b','b'},
                {'c','c','c','e'}
        };
        char[][] validMatrix = generateValidMatrix(input);
        // 输出合法矩阵
        for (char[] row : validMatrix) {
            System.out.println(new String(row));
        }
    }
}

代码说明 #

1. 先复制原矩阵，避免修改原始输入数据；
2. 沿用原solve方法的逻辑标记需要修改的位置，确保修改次数为最小值；
3. 对每个标记位置，收集其上下左右已确定的字符，选择第一个未出现在相邻字符中的小写字母替换，保证相邻字符互不相同；
4. 运行测试用例可直接输出符合要求的合法矩阵。

内容的提问来源于stack exchange，提问作者Learner