Java：代入矩阵中的连续数

Question

我需要一种方法来在矩阵中找到一系列连续的数字，并将它们替换为 1，将所有其他数字替换为 0，就像一条蛇一样移动。让我举一个例子，希望能让它更容易理解：

9 2 9
9 6 8
9 9 4

这个矩阵应该变成：

1 0 0
1 0 0
1 1 0

现在我拥有的是：

public int[][] replace(int[][] numbers, int n) {
    int[][] temp = numbers;
    int cont = 0;
    int cont2 = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i < n - 1 && temp[cont][cont2] == temp[cont + 1][cont2]) {
                numbers[cont][cont2] = 1;
                numbers[cont + 1][cont2] = 1;
                cont++;
            }
            if (j < n - 1 && temp[cont][cont2] == temp[cont][cont2 + 1]) {
                numbers[0][1] = 1;
                numbers[0][0] = 1;
                cont2++;
            }
        }
        cont2 = 0;
    }
    return numbers;
}

它几乎不起作用，只替换前 2 个值，然后由于某种原因停止这样做。我还缺少检查当前号码左侧号码的验证；以及使所有其他数字为 0 的部分，这应该不会太难。

有人知道我需要更改什么才能使这项工作有效吗？

Answer 1

题目说明中已经包含一个issue：有两行数字怎么办？使用 DFS（或 BFS）或任何其他寻路算法可以非常简单地找到解决方案本身。不过这个主题已经很好地涵盖了，所以我不会 post 在这里写任何代码。

Answer 2

很难说，因为你的意图令人困惑，但在你的 for 循环中你有两个连续的 if 语句。由于第一个语句可以更改第二个语句的条件表达式中使用的变量的值，我想知道你是否应该在第二个语句中使用 else 而不是 if？

Answer 3

首先，我发现了一些问题或者我误解了你算法中的一些地方：

public int[][] replace(int[][] numbers, int n) {
    int[][] temp = numbers; // /!\ temp points to the same array as numbers
    int cont = 0;  // why not using i
    int cont2 = 0; // why not using j
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i < n - 1 && temp[cont][cont2] == temp[cont + 1][cont2]) {
                numbers[cont][cont2] = 1; // /!\ temp=numbers is also modified
                numbers[cont + 1][cont2] = 1;
                cont++; // /!\ ~= i*j => index out of bound
            }
            if (j < n - 1 && temp[cont][cont2] == temp[cont][cont2 + 1]) {
                numbers[0][1] = 1; // why fixed indexes ?
                numbers[0][0] = 1;
                cont2++;
            }
        }
        cont2 = 0; // cont2 seems equivalent to j
    }
    return numbers;
}

你想要这样的东西吗（我没测试过）：

public int[][] replace(int[][] numbers, int n) {
    int[][] result=new int[n][n];
    int ref = numbers[0][0];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (numbers[i][j]==ref) {
                boolean isAdj=false;
                if(i>0) isAdj=isAdj || numbers[i-1][j]==ref;
                if(i<n-1) isAdj=isAdj || numbers[i+1][j]==ref;
                if(j>0) isAdj=isAdj || numbers[i][j-1]==ref;
                if(j<n-1) isAdj=isAdj || numbers[i][j+1]==ref;
                if(isAdj) result[i][j]=1;
            }
        }
    }
    return result;
}

Answer 4

你目前的总体想法是（据我所知，不管你的代码中有什么错误）是在一条只向下和向右的路径中寻找相似的数字。这个想法并不适用于所有情况。如果您遇到一组先下降后上升的数字，那么它不会改变所有数字。例如，给定

2 1 2
2 1 2
2 2 2

您的算法将从左上角开始，然后向下然后向右，但不会返回以完成 U 形。

其次，行 int[][] temp = numbers; 表示您对 temp 所做的任何更改都会对 numbers 进行，反之亦然。这就是所谓的浅拷贝，因为只复制引用，而不复制它们引用的数据。您可能需要深拷贝。

简单的答案是使用洪水填充算法。洪水填充基本上是通过尽可能多地搜索整个板来填充任意区域，同时遵循定义要填充区域的规则。在它可以成功探索的任何地方，它都会在该位置放置一个 "breadcrumb"（特殊值），然后您可以返回并将其更改为所需的任何值。

以下洪水填充算法使用深度优先搜索来探索要填充的区域。如果要进行广度优先搜索，只需将堆栈切换为优先队列即可。

import java.awt.Point;   //just an integer based point object for the Stack
import java.util.Stack;   //get the Stack

public int[][] replace(int[][] numbers, int n) {
    int value = numbers[0][0];        //value we are looking for
    int[] rowChange = {-1, 0, 1, 0};  //for easy direction checking
    int[] colChange = {0, 1, 0, -1};

    // for the breadcrumbs; initialized to 0, so make a breadcrumb equal to 1
    // then the resulting breadcrumb matrix will be what you want
    int[][] breadcrumbs = new int[numbers.length][numbers[0].length];
    Stack<Point> toExplore = new Stack<Point>();
    toExplore.push(new Point(0, 0));   //explore the first point

    // we are using Point.y as the row (first index),
    // and Point.x as the column (second index)

    //while there is a location to explore
    while (toExplore.size() > 0) {
        Point center = toExplore.pop();

        // drop a breadcrumb
        breadcrumbs[center.y][center.x] = 1;

        // explore in the 4 cardinal directions
        for (int i = 0; i < 4; i++) {
            int row = center.y + rowChange[i];
            int col = center.x + colChange[i];

            // make sure we haven't already been here (bounds check first)
            if ((row >= 0) && (row < numbers.length) &&    // bounds check
                (col >= 0) && (col < numbers[0].length) &&
                (breadcrumbs[row][col] == 0) &&            // make sure we haven't been there already
                (numbers[row][col] == value))              // make sure it has the right value there
            {
                toExplore.push(new Point(col, row));
            }
        }
    }

    // filled with 1's where we explored and 0's where we didn't
    return breadcrumbs;
}

更新构建并运行代码，它可以工作。

Java：代入矩阵中的连续数

Java: Substitute consecutive numbers in a matrix

java

counter

matrix