计算二维数组中相邻的 -1，而不检查越界的位置（扫雷）

Question

我正在编写一个类似于扫雷的程序。这是在 10x10 二维数组中完成的，并且由于我正在处理约束，所以我只能使用二维数组来编写它。但是，我的 count() 方法出现逻辑错误。 count() 方法 returns 在输入位置周围的网格中找到的 -1 的数量（输入位置是我在 [=23= 中所做的 row 和 column ]，例如，(5, 5)。它也不能检查二维数组边界之外的位置。Here is a visual of what the output of count() should look like.

我还必须使用 count() 和 setCounts()。 setCounts() 遍历整个二维数组，跳过任何 -1 的位置，并调用 count() 方法，将当前位置设置为 count() 方法 returns 的值.

    public int count(int row, int col)
    {
        int value = 0;
        for(int r = -1; r < 2; r++)
        {
            for(int c = -1; c < 2; c++)
            {
                if(c == 0 && r == 0)
                    continue;
                
                int newR = row + c;
                int newC = col + c;

                if(newR < 0 || newR >= array.length && newC < 0 || newC >= array[0].length)
                    continue;
    
                if(array[newR][newC] == -1)
                    value++;
            }
        }
        return value;
    }

    public void setCounts()
    {
        for(int r = 0; r < array.length; r++)
        {
            for(int c = 0; c < array[r].length; c++)
            {
                if(array[r][c] != -1)
                    array[r][c] = count(r, c);
                String formatted = String.format("%2d", array[r][c]);
                System.out.print(formatted + " ");
            }
                System.out.println();
        }
    }

问题在于：

count() 方法错误地计算了我在 main()
setCounts() 打印运行dom 行数后超出范围

我确定它与这段代码有关：

if(newR < 0 || newR >= array.length && newC < 0 || newC >= array[0].length)
                    continue;
    
                if(array[newR][newC] == -1)
                    value++;

当我在 continue 之后的循环中打印 newR 和 newC 时，循环是运行domly 将更多数字添加到 row/column 组合中在 setCounts():

中调用 count() 时，整个输出没有直接模式

00
11
11
00
11
 0 01
12
12
01
12
 0 02
13
13
02
13
 0 03
14
14
03
14
 3 04
15
15
04
15
 0 -1 -1 -1 -1 09
09
 0 
-1 00
...

所以取出打印语句，我得到这个作为输出：

0 -1 -1 0 -1 -1 -1 0 0 0 
0 0 0 0 0 0 -1 0 0 0 
0 -1 0 -1 0 0 0 0 0 0 
0 0 -1 0 0 0 0 0 -1 0 
-1 0 0 0 -1 0 0 0 0 0 
0 0 0 -1 0 0 0 -1 0 0 
0 0 0 0 0 0 -1 0 -1 0 
0 0 0 0 -1 -1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
there are 0 -1s
-----------
 3  3  0 -1  3  3  0 -1  0  0 

/* Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 10
    at Grid3.count(Grid3.java:44)
    at Grid3.setCounts(Grid3.java:58)
    at Grid3.main(Grid3.java:86) */

第一个数组是我用Grid的构造函数创建的数组。当调用 setCounts() 时，程序正在尝试打印的第二个数组正在完成。

我想把它改成：

if(newR < 0 || newR >= array.length)
                    continue;
                    
                if(newC < 0 || newC >= array[0].length)
                    continue;
    
                if(array[newR][newC] == -1)
                    value++;

会起作用：它确实起作用，但不符合逻辑。它消除了 ArrayIndexOutOfBoundsException 错误，但逻辑上不起作用，因为它不计算相邻的 -1 的正确性。它似乎也在向任何 row/column 组合添加更多数字运行domly。我把位置作为 (5, 5) 放在 main() 中，有一次我运行代码，它计算了 6 -1s 但只有 3 -1s 在我放的位置：

-1 0 0 0 0 -1 0 -1 0 0 
0 0 0 0 -1 -1 0 0 0 0 
0 -1 0 0 0 0 0 0 0 0 
0 -1 0 -1 -1 0 0 -1 -1 0 
0 0 0 -1 -1 -1 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
-1 0 0 0 0 0 -1 0 0 0 
0 -1 0 0 0 -1 0 0 0 0 
0 -1 0 0 -1 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
there are 6 -1s

而对于 setCounts()，它打印了一个完整的 10x10 二维数组，但也没有正确计算 -1。对于位置 (0, 0)（在本例中，输出左上角的 3，如下所示），该位置实际上应该具有值 2，因为只有 2 个相邻的 -1，但是它实际上是 3。

 3  0  0  0  0  0 -1  0  0  0 
-1 -1  0  3  0  0  0 -1  0  0 
-1  3  6  3 -1  0  3  0  3  0 
 0  3  0 -1 -1 -1  0 -1  0  0 
 3  0  0  0 -1  3  6  3  3  0 
 3 -1  0  0  0  3  0 -1 -1  0 
-1 -1  3  0  0  0  0  3  3  3 
 0  6  6  0  3  0  0  0 -1  0 
 0  0 -1 -1  0 -1  0  0  0  3 
 0  0  0  3  3  0  3  0  0  0

这是一个完整的输出：

0 0 0 0 0 0 -1 0 0 0 
0 -1 0 0 -1 0 0 0 0 0 
0 -1 0 0 0 -1 0 0 0 0 
0 0 -1 -1 -1 0 0 -1 0 0 
0 0 0 0 0 -1 -1 0 -1 0 
-1 0 0 -1 0 -1 0 0 0 0 
0 0 0 0 0 0 0 0 -1 0 
0 -1 0 0 0 0 0 0 -1 0 
0 0 0 0 0 0 -1 0 -1 0 
0 0 0 0 0 0 0 0 0 0 
there are 2 -1's
-----------
 3  0  0  3  0  0 -1  0  0  0 
 3 -1  0  0 -1  0  0  3  0  0 
 0 -1  6  3  0 -1  3  0  0  0 
 0  0 -1 -1 -1  3  3 -1  0  0 
 0  0  3  3  6 -1 -1  0 -1  0 
-1  0  0 -1  0 -1  3  6  0  3 
 3  3  0  0  3  0  3  3 -1  0 
 0 -1  0  0  0  3  0  3 -1  3 
 0  0  3  0  0  0 -1  0 -1  3 
 0  0  0  0  0  0  0  3  0  3

我不知道我做错了什么。我需要 count() 来正确计算给定位置的相邻 -1。如果它没有正确计算相邻的 -1，那么 setCounts() 在逻辑上将不起作用。我应该对其中一种或两种方法进行哪些更改才能使其正确且合乎逻辑地工作？到目前为止，这是我的代码。

public class Grid
{
    private int [][] array;
    private int max;

    public Grid(int max)
    {
        array = new int[10][10];
        this.max = max;
        setRandom();
    }

    public void setRandom()
    {
        int i = 0;
        while(i < max)
        {
            int r = (int)(Math.random() * 9) + 0;
            int c = (int)(Math.random() * 9) + 0;
            if(array[r][c] != -1)
                {
                    array[r][c] = -1;
                    i++;
                }
        }
    }

    public int count(int row, int col)
    {
        int value = 0;
        for(int r = -1; r < 2; r++)
        {
            for(int c = -1; c < 2; c++)
            {
                if(c == 0 && r == 0)
                    continue;
                
                int newR = row + c;
                int newC = col + c;

                if(newR < 0 || newR >= array.length && newC < 0 || newC >= array[0].length)
                    continue;
    
                if(array[newR][newC] == -1)
                    value++;
            }
        }
        return value;
    }

    public void setCounts()
    {
        for(int r = 0; r < array.length; r++)
        {
            for(int c = 0; c < array[r].length; c++)
            {
                if(array[r][c] != -1)
                    array[r][c] = count(r, c);
                String formatted = String.format("%2d", array[r][c]);
                System.out.print(formatted + " ");
            }
                System.out.println();
        }
    }   

    public void print()
    {
        for(int r = 0; r < array.length; r++)
        {
            for(int c = 0; c < array[r].length; c++)
            {
                System.out.print(array[r][c] + " ");
            }
                System.out.println();
        }
    }


    public static void main(String[] args)  // printing grid
    {
        Grid first = new Grid(20);
        int count = first.count(5, 5);
        first.print();
        System.out.println("there are " + count + " -1s");
        System.out.println("-----------");
        first.setCounts();
    }
}

Answer 1

不使用二维数组可能更容易。或者至少，您可能希望存储一个代表每个单元格的对象，而不仅仅是一个 int。通过这种方式，您可以实现用于计算 Cell-Class.

中特定单元格的相邻单元格的逻辑

这是一个例子（使用映射而不是数组）：

public class Grid {

  public final int width, height;
  private final Map<Coordinate, Cell> cells;

  public Grid(int width, int height) {
    this.width = width;
    this.height = height;
    this.cells = IntStream.range(0, width).boxed()
            .flatMap(column ->
                    IntStream.range(0, height).boxed()
                            .map(row -> new Coordinate(row, column))
            )
            .map(Cell::new)
            .collect(Collectors.toMap(Cell::getCoordinate, Function.identity()));
  }

  public Cell get(int row, int col) {
    return this.cells.get(new Coordinate(row, col));
  }

  public class Cell {
    private final Coordinate coordinate;
    private final boolean isMine;

    public Cell(Coordinate coordinate, boolean isMine) {
        this.coordinate = coordinate;
        this.isMine = isMine;
    }

    public Cell(Coordinate coordinate) {
        this(coordinate, new Random().nextBoolean());
    }

    public Coordinate getCoordinate() {
        return coordinate;
    }

    public List<Cell> getNeighbours() {
        int leftNeighbourColumnIdx = coordinate.column - 1;
        int topNeighbourRowIdx = coordinate.row - 1;
        return IntStream.range(leftNeighbourColumnIdx, leftNeighbourColumnIdx + 3).boxed()
                .flatMap(column -> IntStream.range(topNeighbourRowIdx, topNeighbourRowIdx + 3).boxed().map(row -> new Coordinate(row, column)))
                .map(Grid.this.cells::get)
                .filter(Objects::nonNull)
                .filter(c -> !c.equals(this))
                .collect(Collectors.toList());
    }

    public int countNeighbouringMines() {
        return (int) getNeighbours().stream()
                .filter(cell -> cell.isMine)
                .count();
    }
  }

  public static class Coordinate {
    private final int row, column;

    public Coordinate(int row, int column) {
        this.row = row;
        this.column = column;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Coordinate that = (Coordinate) o;
        return row == that.row && column == that.column;
    }

    @Override
    public int hashCode() {
        return Objects.hash(row, column);
    }
  }


  public static void main(String[] args) {
    final var grid = new Grid(10, 10);
    for (int row = 0; row < grid.height; row++) {
        for (int col = 0; col < grid.width; col++) {
            final var cell = grid.get(row, col);
            System.out.print(cell.isMine ? "x" : "o");
            System.out.print(" ");
        }
        System.out.println();
    }

    System.out.printf("mines around (5,5): %d%n", grid.get(5, 5).countNeighbouringMines());
  }

}

编辑：与上面相同的示例，但使用二维数组而不是地图

public class Grid {

    public final int width, height;
    private final Cell[][] cells;

    public Grid(int width, int height) {
        this.width = width;
        this.height = height;
        cells = new Cell[width][height];

        IntStream.range(0, width)
                .forEach(column -> IntStream.range(0, height)
                        .forEach(row -> cells[column][row] = new Cell(column, row))
                );
    }

    public Cell get(int row, int col) {
        final var column = col < 0 || col >= this.cells.length ? null : this.cells[col];
        return row < 0 || column == null || row >= column.length ? null : column[row];
    }

    public class Cell {
        private final int column, row;
        private final boolean isMine;

        public Cell(int column, int row, boolean isMine) {
            this.column = column;
            this.row = row;
            this.isMine = isMine;
        }

        public Cell(int column, int row) {
            this(column, row, new Random().nextBoolean());
        }

        public List<Cell> getNeighbours() {
            int leftNeighbourColumnIdx = column - 1;
            int topNeighbourRowIdx = row - 1;
            return IntStream.range(leftNeighbourColumnIdx, leftNeighbourColumnIdx + 3).boxed()
                    .flatMap(column -> IntStream.range(topNeighbourRowIdx, topNeighbourRowIdx + 3).boxed()
                            .map(row -> Grid.this.get(row, column)))
                    .filter(Objects::nonNull)
                    .filter(c -> !c.equals(this))
                    .collect(Collectors.toList());
        }

        public int countNeighbouringMines() {
            return (int) getNeighbours().stream()
                    .filter(cell -> cell.isMine)
                    .count();
        }
    }


    public static void main(String[] args) {
        final var grid = new Grid(10, 10);
        for (int row = 0; row < grid.height; row++) {
            for (int col = 0; col < grid.width; col++) {
                final var cell = grid.get(row, col);
                System.out.print(cell.isMine ? "x" : "o");
                System.out.print(" ");
            }
            System.out.println();
        }

        System.out.printf("mines around (5,5): %d%n", grid.get(5, 5).countNeighbouringMines());
    }
}

想法是，Grid returns 中的 get(int row, int col) 方法要么是 Cell 对象，要么是 null 如果 row 或 cell 无效——但它永远不会失败（抛出异常）。然后每个单元格都可以使用此方法尝试获取其所有邻居 (getNeighbours())。单元格不需要担心它请求的 row/column 是否有效——这将由 get(int row, int col) 处理。它只需要过滤掉所有 null 值（那些坐标无效）和它本身。

使用 getNeighbours()，您有一个包含所有相邻单元格的列表。如果你过滤掉所有没有地雷的单元格——你会得到一个带有地雷的邻居列表——然后你只需要计算它们。

计算二维数组中相邻的 -1，而不检查越界的位置（扫雷）

Counting adjacent -1s in a 2d array without checking positions that are out of bounds (Minesweeper)

java

arrays

matrix

multidimensional-array

编辑：与上面相同的示例，但使用二维数组而不是地图