矩阵连接的单元格：给定矩阵的位置，用数字 k 替换连接的单元格

Question

问题陈述：给定一个1和0的矩阵和位置（行，列），替换从该位置到k

的所有连接单元格

输入：

行 = 1，列 = 2，k = 2 输出：

使用的方法：递归检查左侧、右侧、顶部和底部单元格并将单元格更新为 k。但是对于角单元格，输出不是预期的，我不知道哪里出了问题，谁能帮我弄清楚哪里出了问题？

行 = 0，列 = 1，k = 2 错误输出：

预期输出：

import java.util.Arrays;

public class MatrixProblem {

    public static int[][] updateColor(int[][] num, int row, int col, int k) {
        int[][] sol = num.clone();
        updateMat(row,col,num[row][col],k,sol);
        return sol;
    }

    private static void updateMat(int row, int col, int o,int k, int[][] sol) { // o stands for old value
        sol[row][col] = k;
        if(row<0 || col<0 || row>= sol.length || col>= sol[row].length) {
            return;
        }
        if (leftPresent(row,col,o,sol)) {
            updateMat(row,--col,o,k,sol);
        }
        if(rightPresent(row,col,o,sol)) {
            updateMat(row,++col,o,k,sol);
        }
        if(topPresent(row,col,o,sol)) {
            updateMat(--row,col,o,k,sol);
        }
        if(bottomPresent(row,col,o,sol)) {
            updateMat(++row,col,o,k,sol);
        }
    }

    private static boolean leftPresent(int row,int col,int old, int[][] sol) {
        int newCol = --col;
        if(newCol >= 0 && sol[row][newCol] == old) {
            return true;
        }
        return false;
    }

    private static boolean rightPresent(int row,int col,int old, int[][] sol) {
        int newCol = ++col;
        if(newCol < sol[row].length && sol[row][newCol] == old) {
            return true;
        }
        return false;
    }
    private static boolean topPresent(int row,int col,int old, int[][] sol) {
        int newRow= --row;      
        if(newRow>=0  && sol[newRow][col] == old) {
            return true;
        }
        return false;
    }
    private static boolean bottomPresent(int row,int col,int old, int[][] sol) {
        int newRow = ++row;
        if(newRow < sol.length && sol[newRow][col] == old) {
            return true;
        }
        return false;
    }
    public static void main (String[] args) {
        int[][] num = new int[][]{{0,0,0,0},
                                   {0,0,1,0},
                                   {0,1,1,0},
                                   {0,0,0,0}};

            System.out.println(Arrays.deepToString(num1));
            System.out.println(Arrays.deepToString(updateColor(num,1,2,2))); //  row = 1, col = 2 , k = 2
            System.out.println(Arrays.deepToString(num2));
            System.out.println(Arrays.deepToString(updateColor(num,0,1,2))); // row =0 , col=1 , k = 2

    }
}

Answer 1

问题是因为您使用了前缀 increment/decrement 运算符

updateMat(row,--col,o,k,sol);

下次您在同一函数中使用 col 时，它必须比实际值小 1。在进行递归调用时，您必须 increment/decrement row/col 值，而不影响 updateMat 函数中的 curent 局部变量。

例子：当你从 (0, 1) 开始，你调用 updateMat 后，col 变成 0。然后你检查 right ，顶部和底部，因此你永远不会到达 (0, 2)。

试试这个..

if (leftPresent(row,col,o,sol)) {
    updateMat(row, col - 1, o, k, sol);
}
if(rightPresent(row,col,o,sol)) {
     updateMat(row, col + 1, o, k, sol);
}
if(topPresent(row,col,o,sol)) {
    updateMat(row - 1, col, o, k, sol);
}
if(bottomPresent(row,col,o,sol)) {
    updateMat(row + 1, col, o, k, sol);
}

您在每个辅助函数 leftPresent 等中执行相同的操作，但不会产生 bug/issue。但为了清楚起见，我建议也更改它。

Answer 2

评论中讨论的是我的版本。

package fun;
import static java.lang.System.out;

public class Fun {
    public static void main(String[] args) {
        int[][] matrix = {
                            {0,0,0,0},
                            {0,0,1,0},
                            {0,1,1,0},
                            {0,0,0,0}           
                         };

        out.println("Initial State");

        for(int i=0;i<matrix.length;++i){
            for(int j=0;j<matrix[i].length;++j){
                out.print(matrix[i][j] + " ");
            }
            out.println();
        }

        // apply depth first search(dfs) to modify connected cells
        updateValues(matrix,0,1,5);

        out.println("Modified State");

        for(int i=0;i<matrix.length;++i){
            for(int j=0;j<matrix[i].length;++j){
                out.print(matrix[i][j] + " ");
            }
            out.println();
        }
    }

    private static void updateValues(int[][] matrix,int row,int col,int new_value){
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];// by default every value is false.
        dfs(matrix,row,col,matrix[row][col],new_value,visited);
    }

    private static void dfs(int[][] matrix,int row,int col,int old_value,int new_value,boolean[][] visited){
        if(!isValidLocation(row,col,matrix.length,matrix[0].length)) return;// if index is valid and not going out of bounds
        if(matrix[row][col] != old_value) return;// since this cell isn't connected.
        if(visited[row][col]) return;// not visiting the same index again once it's visited.

        visited[row][col] = true;// mark visited
        matrix[row][col] = new_value;// modify to new value

        dfs(matrix,row-1,col,old_value,new_value,visited);// up
        dfs(matrix,row+1,col,old_value,new_value,visited);// down
        dfs(matrix,row,col-1,old_value,new_value,visited);// left
        dfs(matrix,row,col+1,old_value,new_value,visited);// right
    }   

    private static boolean isValidLocation(int row,int col,int row_size,int col_size){
        return row >= 0 && row < row_size && col >= 0 && col < col_size;
    }    
}

输出

Initial State
0 0 0 0 
0 0 1 0 
0 1 1 0 
0 0 0 0 
Modified State
5 5 5 5 
5 5 1 5 
5 1 1 5 
5 5 5 5

矩阵连接的单元格：给定矩阵的位置，用数字 k 替换连接的单元格

Matrix Connected Cells: Given the position of the matrix replace connected cells with number k

java

algorithm

depth-first-search