Giả sử chúng ta có một mê cung hình vuông chứa đầy các con số; chúng ta phải tìm tất cả các đường đi từ ô góc đến ô giữa. Ở đây, chúng ta sẽ tiến hành chính xác n bước từ một ô theo 4 hướng Lên, Xuống, Phải và Trái với n là giá trị của ô đó. Do đó, chúng ta có thể di chuyển từ ô [i + n, j] sang [i-n, j], [i, j + n] và [i, j-n] từ ô [i, j] trong đó n là giá trị của ô [ tôi, j].
Vì vậy, nếu đầu vào giống như
| 3 | 4 | 4 | 4 | 7 | 3 | 4 | 6 | 3 |
| 6 | 7 | 5 | 6 | 6 | 2 | 6 | 6 | 2 |
| 3 | 3 | 4 | 3 | 2 | 5 | 4 | 7 | 2 |
| 6 | 5 | 5 | 1 | 2 | 3 | 6 | 5 | 6 |
| 3 | 3 | 4 | 3 | 0 | 1 | 4 | 3 | 4 |
| 3 | 3 | 4 | 3 | 2 | 1 | 3 | 3 | 5 |
| 3 | 5 | 4 | 3 | 2 | 6 | 4 | 4 | 3 |
| 3 | 5 | 1 | 3 | 7 | 5 | 3 | 6 | 3 |
| 6 | 2 | 4 | 3 | 4 | 5 | 4 | 5 | 1 |
thì đầu ra sẽ là
-
(0, 0) → (0, 3) → (0, 7) → (6, 7) → (6, 3) → (3, 3) → (3, 4) → (5, 4) → (5 , 2) → (1, 2) → (1, 7) → (7, 7) → (7, 1) → (2, 1) → (5, 1) → (0, 1) → (4, 1 ) → (4, 4) → TRUNG GIAN
-
(0, 0) → (0, 3) → (0, 7) → (6, 7) → (6, 3) → (3, 3) → (3, 4) → (5, 4) → (5 , 2) → (1, 2) → (1, 7) → (7, 7) → (7, 1) → (2, 1) → (2, 4) → (4, 4 → TRUNG GIAN
-
(0, 0) → (0, 3) → (0, 7) → (0, 1) → (4, 1) → (7, 1) → (2, 1) → (2, 4) → (4 , 4) → TRUNG BÌNH
-
(0, 0) → (0, 3) → (0, 7) → (0, 1) → (4, 1) → (4, 4) → TRUNG BÌNH
-
(8, 8) → (7, 8) → (4, 8) → (4, 4) → TRUNG GIAN
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
N:=9
-
Xác định một hàm is_ok (), hàm này sẽ sử dụng một tập hợp các cặp được gọi là đã thăm, một cặp pt,
-
trả về true khi phần tử đầu tiên và thứ hai của pt trong phạm vi từ 0 đến N và pt không được truy cập
-
Xác định mảng dir_row:={- 1, 1, 0, 0}
-
Xác định mảng dir_col:={0, 0, - 1, 1}
-
Xác định một hàng mảng:={0, 0, N - 1, N - 1}
-
Xác định một mảng col:={0, N - 1, 0, N - 1}
-
Xác định một hàm giải quyết (), hàm này sẽ lấy mê cung, đường dẫn, một tập hợp các cặp được truy cập, một cặp curr,
-
nếu đầu tiên và thứ hai của curr giống N / 2, thì -
-
hiển thị đường dẫn
-
trở lại
-
-
để khởi tạo i:=0, khi i <4, cập nhật (tăng i lên 1), thực hiện -
-
n:=mê cung [curr.first, curr.second]
-
x:=curr.first + dir_row [i] * n
-
y:=curr.second + dir_col [i] * n
-
n:=một cặp sử dụng x, y
-
if is_ok (đã thăm, tiếp theo), thì -
-
chèn tiếp theo vào đã truy cập
-
chèn tiếp theo ở cuối đường dẫn
-
giải quyết (mê cung, đường dẫn, đã thăm, tiếp theo)
-
xóa phần tử cuối cùng khỏi đường dẫn
-
xóa tiếp theo khỏi đã truy cập
-
-
-
Từ phương thức chính, thực hiện như sau -
-
Xác định một tập hợp các cặp được gọi là đã truy cập
-
để khởi tạo i:=0, khi i <4, cập nhật (tăng i lên 1), thực hiện -
-
x:=row [i]
-
y:=col [i]
-
pt:=tạo một cặp bằng cách sử dụng (x, y)
-
chèn pt vào đã truy cập
-
chèn pt vào cuối đường dẫn
-
giải quyết (mê cung, đường dẫn, đã thăm, pt)
-
xóa phần tử cuối cùng khỏi đường dẫn
-
xóa pt khỏi đã truy cập
-
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#include <bits/stdc++.h>
using namespace std;
#define N 9
bool is_ok(set<pair<int, int> > visited, pair<int, int> pt) {
return (pt.first >= 0) && (pt.first < N) && (pt.second >= 0) && (pt.second < N) && (visited.find(pt) == visited.end());
}
void display_path(list<pair<int, int> > path) {
for (auto it = path.begin(); it != path.end(); it++)
cout << "(" << it->first << ", " << it->second << ")->";
cout << "MIDDLE" << endl << endl;
}
int dir_row[] = {-1, 1, 0, 0};
int dir_col[] = { 0, 0, -1, 1};
int row[] = { 0, 0, N-1, N-1};
int col[] = { 0, N-1, 0, N-1};
void solve(int maze[N][N], list<pair<int, int> > &path, set<pair<int, int> > &visited, pair<int, int> &curr) {
if (curr.first == N / 2 && curr.second == N / 2) {
display_path(path);
return;
}
for (int i = 0; i < 4; ++i) {
int n = maze[curr.first][curr.second];
int x = curr.first + dir_row[i]*n;
int y = curr.second + dir_col[i]*n;
pair<int, int> next = make_pair(x, y);
if (is_ok(visited, next)) {
visited.insert(next);
path.push_back(next);
solve(maze, path, visited, next);
path.pop_back();
visited.erase(next);
}
}
}
void search_path(int maze[N][N]) {
list<pair<int, int> > path;
set<pair<int, int> > visited;
for (int i = 0; i < 4; ++i) {
int x = row[i];
int y = col[i];
pair<int, int> pt = make_pair(x, y);
visited.insert(pt);
path.push_back(pt);
solve(maze, path, visited, pt);
path.pop_back();
visited.erase(pt);
}
}
int main() {
int maze[N][N] = {
{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}
};
search_path(maze);
} Đầu vào
{{3, 4, 4, 4, 7, 3, 4, 6, 3},
{6, 7, 5, 6, 6, 2, 6, 6, 2},
{3, 3, 4, 3, 2, 5, 4, 7, 2},
{6, 5, 5, 1, 2, 3, 6, 5, 6},
{3, 3, 4, 3, 0, 1, 4, 3, 4},
{3, 5, 4, 3, 2, 1, 3, 3, 5},
{3, 5, 4, 3, 2, 6, 4, 4, 3},
{3, 5, 1, 3, 7, 5, 3, 6, 3},
{6, 2, 4, 3, 4, 5, 4, 5, 1}} Đầu ra
(0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(5, 1)->(0, 1)->(4, 1)->(4, 4)->MIDDLE (0, 0)->(0, 3)->(0, 7)->(6, 7)->(6, 3)->(3, 3)->(3, 4)->(5, 4)->(5, 2)->(1, 2)->(1, 7)->(7, 7)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE (0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(7, 1)->(2, 1)->(2, 4)->(4, 4)->MIDDLE (0, 0)->(0, 3)->(0, 7)->(0, 1)->(4, 1)->(4, 4)->MIDDLE (8, 8)->(7, 8)->(4, 8)->(4, 4)->MIDDLE