Chuột trong mê cung với nhiều bước hoặc nhảy được phép

Bài toán chuột trong mê cung là một trong những bài toán nổi tiếng của thuật toán quay lui (backtracking). Ở đây chúng ta sẽ xem bài toán đó với một chút biến thể. Giả sử một mê cung NxN M được cho. Điểm xuất phát là góc trên bên trái M[0, 0], và đích đến là góc dưới bên phải M[N-1, N-1]. Một con chuột được đặt tại điểm xuất phát. Mục tiêu của chúng ta là tìm một đường đi từ điểm xuất phát đến điểm kết thúc mà chuột có thể đi để đến đích. Ở đây chuột có thể nhảy (biến thể). Bây giờ có một số ràng buộc:

Chuột chỉ có thể di chuyển sang phải hoặc xuống dưới.
Ô có giá trị 0 trong mê cung biểu thị ô bị chặn.
Các ô khác 0 biểu thị đường đi hợp lệ.
Số bên trong ô biểu thị số bước nhảy tối đa chuột có thể thực hiện từ ô đó.

Thuật toán

ratInMaze

begin
  if destination is reached, then
    print the solution matrix
  else
    1. Place the current cell inside the solution matrix as 1
    2. Move forward or jump (check max jump value) and recursively check if move leads to solution or not.
    3. If the move taken from the step 2 is not correct, then move down, and check it leads to the solution or not
    4. If none of the solutions in step 2 and 3 are correct, then make the current cell 0.
  end if
end

Ví dụ

#include <iostream>
#define N 4
using namespace std;

void dispSolution(int sol[N][N]) {
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++)
      cout << sol[i][j] << " ";
    cout << endl;
  }
}

bool isSafe(int maze[N][N], int x, int y) {
  //check whether x,y is valid or not
  // when (x, y) is outside of the maze, then return false
  if (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] != 0)
    return true;
  return false;
}

bool ratMazeSolve(int maze[N][N], int x, int y, int sol[N][N]) {
  if (x == N - 1 && y == N - 1) { //if destination is found, return true
    sol[x][y] = 1;
    return true;
  }
  if (isSafe(maze, x, y)) {
    sol[x][y] = 1; //mark 1 into solution matrix
    for (int i = 1; i <= maze[x][y] && i < N; i++) {
      if (ratMazeSolve(maze, x + i, y, sol)) //move right
        return true;
      if (ratMazeSolve(maze, x, y + i, sol)) //move down
        return true;
    }
    sol[x][y] = 0; //if the solution is not valid, then make it 0
    return false;
  }
  return false;
}

bool solveMaze(int maze[N][N]) {
  int sol[N][N] = { { 0, 0, 0, 0 },
    { 0, 0, 0, 0 },
    { 0, 0, 0, 0 },
    { 0, 0, 0, 0 }
  };
  if (!ratMazeSolve(maze, 0, 0, sol)) {
    cout << "Solution doesn't exist";
    return false;
  }
  dispSolution(sol);
  return true;
}

main() {
  int maze[N][N] = { { 2, 1, 0, 0 },
    { 3, 0, 0, 1 },
    { 0, 1, 0, 1 },
    { 0, 0, 0, 1 }
  };
  solveMaze(maze);
}

Kết quả