java - 用于计算 X 到 Y 网格中路径数的算法

Question

我想用Java创建一个程序，计算机器人可以从网格T（x，y）的左上角到左下角的路径数..只使用网格中的每个正方形并使用所有正方形在网格中。机器人可以左右上下移动，使其更加复杂。我知道这是一个递归程序，我只是不知道如何实现它。

Answer 1

您需要跟踪空闲方格的数量，当您到达左下角时，检查您是否用完所有方格。

static int countPaths(boolean[][] grid) {
    int freeSquares = 0;
    for(int y = 0; y < grid.length; y++) {
        for(int x = 0; x < grid[y].length; x++) {
            if(grid[y][x]) freeSquares++;
        }
    }
    return _countPaths(grid, 0, 0, freeSquares);
}

static int _countPaths(boolean[][] grid, int x, int y, int freeSquares) {
    if(!grid[y][x]) return 0;
    if(y == grid.length-1 && x == 0) { // bottom left
        if(freeSquares == 1) return 1;
        else return 0;
    }
    int sum = 0;
    grid[y][x] = false;
    for(int dy = -1; dy <= 1; dy++) {
        for(int dx = -1; dx <= 1; dx++) {
            int newX = x+dx, newY = y+dy;
            if(newX < 0 || newY < 0 || newY >= grid.length || newX >= grid[y].length) continue;
            if((dx == 0 && dy == 0) || (dx != 0 && dy != 0)) continue;
            sum += _countPaths(grid, x+dx, y+dy, freeSquares-1);
        }
    }
    grid[y][x] = true;
    return sum;
}

public static void main (String args[]) {
    boolean[][] grid = {{true, true, true, false},
                        {true, true, true, false},
                        {true, true, true,  true},
                        {true, true, true,  true}};
    System.out.println(countPaths(grid));
}

Answer 2

那么，你需要知道什么？您需要知道电路板的当前状态以及机器人的位置。从那里，您可以探索尚未访问过的每个相邻单元格。当您探索每个单元格时，递归地应用该算法来探索它们的相邻单元格。最终，每次探索要么找到目标，要么耗尽机会。

基本算法将如下所示：

explore(board, position) {
  if (position == goal) {
    count++
    return
  }
  board.mark(position)
  for cell in position.neighbors
     if not board.ismarked(cell)
       explore(board, cell)
  board.unmark(position)
}