CODEWITHSUNDEEP
javaarraysfunctionrecursionshortest-path
Invisible
Invisible

Reputation: 112

Java Maze Shortest Path misunderstanding

Here is code, using recursion, I am trying to solve maze with shortest pathing, but it is getting solved with a longer way and I don't really understand why. Here is code of recursion : 

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;

}

it's 8x8 board, the block function works like this: 

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();
}

}

When I try to solve it gives me someting like this : enter image description here

instead of : enter image description here

Any help would be greatly appriecated!

Upvotes: 1

Views: 128

Answers (1)

George Dirac
George Dirac

Reputation: 178

Try this, it should work and go straight to finish:

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;
}

You needed to change orders.

Upvotes: 2

Related Questions