Java迷宫最短路径误解

Question

这是代码，使用递归，我试图用最短路径解决迷宫问题，但它正在用更长的路径解决，我真的不明白为什么。这是递归代码：

public boolean findPath(int row, int col) {
board[row][col].visit();

if ((col == 7) && (row == 7)) {
  board[row][col].selectCell();
  return true;
}


if ((row > 0) && !board[row - 1][col].marked() &&
    !board[row - 1][col].blocked() && !board[row - 1][col].visited()) {
  block(row, col);

  if (findPath(row - 1, col)) {
    board[row][col].selectCell();
    return true;
  }

  unblock(row, col);
}

if ((row < 7) && !board[row + 1][col].marked() &&
    !board[row + 1][col].blocked() && !board[row + 1][col].visited()) {
  block(row, col);

  if (findPath(row + 1, col)) {
    board[row][col].selectCell();
    return true;
  }

  unblock(row, col);
}

if ((col > 0) && !board[row][col - 1].marked() &&
    !board[row][col - 1].blocked() && !board[row][col - 1].visited()) {
  block(row,col);
  if (findPath(row, col - 1)) {
    board[row][col].selectCell();
    return true;
  }

  unblock(row,col);
}

if ((col < 7) && !board[row][col + 1].marked() &&
    !board[row][col + 1].blocked() && !board[row][col + 1].visited()) {
  block(row,col);
  if (findPath(row, col + 1)) {
    board[row][col].selectCell();
    return true;
  }

  unblock(row,col);
}

return false;

}

它是 8x8 板，块功能是这样的：

public void block(int row, int col) {
if (row > 0) {
  board[row - 1][col].block();
}

if (row < 7) {
  board[row + 1][col].block();
}

if (col > 0) {
  board[row][col - 1].block();
}

if (col < 7) {
  board[row][col + 1].block();
}

}

当我尝试解决它时，它给了我这样的东西：

而不是：

如有任何帮助，我们将不胜感激！

Answer 1

试试这个，它应该可以直接完成：

public boolean findPath(int row, int col) {
  board[row][col].visit();

  if ((col == 7) && (row == 7)) {
    board[row][col].selectCell();
    return true;
  }

  if ((row < 7) && !board[row + 1][col].marked() &&
      !board[row + 1][col].blocked() && !board[row + 1][col].visited()) {
    block(row, col);

    if (findPath(row + 1, col)) {
      board[row][col].selectCell();
      return true;
    }

    unblock(row, col);
  }

  if ((col > 0) && !board[row][col - 1].marked() &&
      !board[row][col - 1].blocked() && !board[row][col - 1].visited()) {
    block(row,col);

    if (findPath(row, col - 1)) {
      board[row][col].selectCell();
      return true;
    }

    unblock(row,col);
  }

  if ((col < 7) && !board[row][col + 1].marked() &&
      !board[row][col + 1].blocked() && !board[row][col + 1].visited()) {
    block(row,col);

    if (findPath(row, col + 1)) {
      board[row][col].selectCell();
      return true;
    }

    unblock(row,col);
  }
  if ((row > 0) && !board[row - 1][col].marked() &&
      !board[row - 1][col].blocked() && !board[row - 1][col].visited()) {
    block(row, col);

    if (findPath(row - 1, col)) {
      board[row][col].selectCell();
      return true;
    }

    unblock(row, col);
  }

  return false;
}

您需要更改订单。

Java迷宫最短路径误解

Java Maze Shortest Path misunderstanding

java

arrays

recursion

function

shortest-path