Bài toán Chuột trong Lỗ (Rat in a Maze)

Giới thiệu

Cho mê cung NxN, ô (0,0) là bắt đầu, ô (N-1,N-1) là đích. Ô giá trị 1 là đường đi, 0 là tường. Chuột chỉ đi phải hoặc xuống. Tìm đường đi nếu có, đánh dấu đường đi.

Đầu vào và Đầu ra

Đầu vào: Ma trận mê cung, 1 = đường, 0 = tường. 
Đầu ra: Ma trận đường đi (1 = trên đường đi).

Thuật toán

isValid(x, y)

Begin
  nếu x,y trong phạm vi VÀ (x,y) không bị chặn thì return true
  return false
End

solveRatMaze(x, y)

Begin
  nếu (x,y) là góc phải dưới thì đánh dấu 1, return true
  nếu isValid(x,y) thì
    đánh dấu (x,y) = 1
    nếu solveRatMaze(x+1, y) thì return true  // đi phải
    nếu solveRatMaze(x, y+1) thì return true  // đi xuống
    đánh dấu (x,y) = 0 (backtrack)
    return false
  return false
End

Ví dụ (C++)

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

int maze[N][N] = {
  {1, 0, 0, 0, 0},
  {1, 1, 0, 1, 0},
  {0, 1, 1, 1, 0},
  {0, 0, 0, 1, 0},
  {1, 1, 1, 1, 1}
};

int sol[N][N];

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

bool isValidPlace(int x, int y) {
  return (x >= 0 && x < N && y >= 0 && y < N && maze[x][y] == 1);
}

bool solveRatMaze(int x, int y) {
  if(x == N-1 && y == N-1) { sol[x][y] = 1; return true; }
  if(isValidPlace(x, y)) {
    sol[x][y] = 1;
    if (solveRatMaze(x+1, y)) return true;
    if (solveRatMaze(x, y+1)) return true;
    sol[x][y] = 0; return false;
  }
  return false;
}

bool findSolution() {
  if(!solveRatMaze(0, 0)) { cout << "There is no path"; return false; }
  showPath(); return true;
}

int main() { findSolution(); }

Kết quả đầu ra