浏览矩阵 / 李氏算法

huangapple go评论79阅读模式
英文:

Browse the matrix / Lee Algorithm

问题

我必须编写一个方法来遍历这个矩阵。我从键盘输入位置[L,C]的坐标,从这个位置开始进行扩展。只有在下一个值小于当前值时,才会移动到下一个值。不会沿对角线移动!
PS:对于我的英语表示抱歉。
就像图片中所示:
enter image description here

英文:

I have to do a method that will go through the matrix.I give the coordinates from the keyboard of the position [L, C], from where the extension will start.It will pass to the next value only if the next value is smaller than this.On the diagonals do not go!
PS: Sorry for my english
Like in image:
enter image description here

答案1

得分: 1

// 准备输出矩阵并用-1填充
int[][] outMatrix = prepareOut(inputArray.length, inputArray[0].length);

// 从初始坐标开始递归调用方法标记单元格
outMatrix = markCell(inputArray, outMatrix, line, column, 1);

// 打印输出矩阵
printOutput(outMatrix);

最相关的方法实现可能如下所示:

    static int[][] markCell(int[][] arr, int[][] out, int y, int x, int move) {
        int val = arr[y][x];
        if (out[y][x] == 0) {
            return out;
        } else if (out[y][x] < 0) {
            out[y][x] = move;
        }

        // 检查当前单元格上方的单元格(北)
        if (y > 0 && out[y - 1][x] < 0) {
            if (cellMarked(arr, out, y - 1, x, val, move)) {
                out = markCell(arr, out, y -1, x, move + 1);
            }
        }
        // 检查当前单元格下方的单元格(南)
        if (y < arr.length - 1 && out[y + 1][x] < 0) {
            if (cellMarked(arr, out, y + 1, x, val, move)) {
                out = markCell(arr, out, y +1, x, move + 1);
            }
        }
        // 检查当前单元格左侧的单元格(西)
        if (x > 0 && out[y][x - 1] < 0) {
            if (cellMarked(arr, out, y, x - 1, val, move)) {
                out = markCell(arr, out, y, x - 1, move + 1);
            }
        }
        // 检查当前单元格右侧的单元格(东)
        if (x < arr[0].length - 1 && out[y][x + 1] < 0) {
            if (cellMarked(arr, out, y, x +1, val, move)) {
                out = markCell(arr, out, y, x + 1, move + 1);
            }
        }
        return out;
    }

   static boolean cellMarked(int[][] arr, int[][] out, int y, int x, int val, int move) {
        final boolean marked = arr[y][x] <= val;
        out[y][x] = marked ? move : 0;
        return marked;
    }

在打印输出矩阵时,将剩余的-1替换为0:

    static void printOutput(int[][] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                char c = arr[i][j] <= 0 ? '0' : '*';
                System.out.print(c);
                System.out.print('\t');
            }
            System.out.print('\n');
        }
    }
英文:

Three steps need to be done here:

// prepare output matrix and fill it with -1
int[][] outMatrix = prepareOut(inputArray.length, inputArray[0].length);
// call recursively method to mark cells starting from the initial coordinates
outMatrix = markCell(inputArray, outMatrix, line, column, 1);
// print output matrix
printOutput(outMatrix);

The most relevant method implementation may be like this:

    static int[][] markCell(int[][] arr, int[][] out, int y, int x, int move) {
int val = arr[y][x];
if (out[y][x] == 0) {
return out;
} else if (out[y][x] &lt; 0) {
out[y][x] = move;
}
// checking a cell above the current one (north)
if (y &gt; 0 &amp;&amp; out[y - 1][x] &lt; 0) {
if (cellMarked(arr, out, y - 1, x, val, move)) {
out = markCell(arr, out, y -1, x, move + 1);
}
}
// checking a cell under the current one (south)
if (y &lt; arr.length - 1 &amp;&amp; out[y + 1][x] &lt; 0) {
if (cellMarked(arr, out, y + 1, x, val, move)) {
out = markCell(arr, out, y +1, x, move + 1);
}
}
// checking a cell to the left of the current one (west)
if (x &gt; 0 &amp;&amp; out[y][x - 1] &lt; 0) {
if (cellMarked(arr, out, y, x - 1, val, move)) {
out = markCell(arr, out, y, x - 1, move + 1);
}
}
// checking a cell to the right of the current one (east)
if (x &lt; arr[0].length - 1 &amp;&amp; out[y][x + 1] &lt; 0) {
if (cellMarked(arr, out, y, x +1, val, move)) {
out = markCell(arr, out, y, x + 1, move + 1);
}
}
return out;
}
static boolean cellMarked(int[][] arr, int[][] out, int y, int x, int val, int move) {
final boolean marked = arr[y][x] &lt;= val;
out[y][x] = marked ? move : 0;
return marked;
}

When printing the output matrix, you replace remaining -1 with 0:

    static void printOutput(int[][] arr) {
for (int i = 0; i &lt; arr.length; i++) {
for (int j = 0; j &lt; arr[i].length; j++) {
char c = arr[i][j] &lt;= 0 ? &#39;0&#39; : &#39;*&#39;;
System.out.print(c);
System.out.print(&#39;\t&#39;);
}
System.out.print(&#39;\n&#39;);
}
}

答案2

得分: 0

prepareOut可以像这样实现:

    private static int[][] prepareOut(int rows, int cols) {
        int [][] out = new int[rows][cols];
        for(int[] row: out) {
            Arrays.fill(row, -1);
        }
        return out;
    }
英文:

prepareOut may be implemented like this:

    private static int[][] prepareOut(int rows, int cols) {
int [][] out = new int[rows][cols];
for(int[] row: out) {
Arrays.fill(row, -1);
}
return out;
}

huangapple
  • 本文由 发表于 2020年4月10日 20:36:40
  • 转载请务必保留本文链接:https://go.coder-hub.com/61140380.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定