Bài toán kiểm tra tồn tại đường đi từ vị trí A đến vị trí B cho trước trong ma trận
Xin chào mọi người. Mình có đang giải 1 problem sau: http://ntucoder.net/Problem/Details/107
Mình quyết định giải bài này theo hướng từ vị trí A(x0; y0) cho trước ta sẽ gọi đệ quy 4 lần để nhích lên ô trên, ô dưới, ô trái và ô phải. Điều kiện tìm được khi tọa độ (x0; y0) = (x1; y1) với B(x1; y1) là điểm đích đã cho trước.
Và để tránh trường hợp nhích ngược trở lại, tức là A(x0; y0) nhích lên trên 1 ô thành A'(x0'; y0) rồi lại nhích xuống A(x0; y0) lần nữa (do cách cài đặt đệ quy), mình sẽ bỏ 4 tham số top, bot, left, right vào cho hàm đệ quy để kiểm tra.
Cách cài đặt thuật toán của mình như sau: https://ideone.com/RtoUDG
#include <iostream>
#include <vector>
using namespace std;
int n, dy, dx;
bool findway(vector<vector<int>> arr, int sy, int sx, int top = 0, int bot = 0, int left = 0, int right = 0)
{
if (sy == (dy - 1) && sx == (dx - 1)) return true;
// left
if (sx >= 1 && arr[sy][sx - 1] == 0 && left == 0) {
if (findway(arr, sy, sx - 1, 0, 0, 0, 1))
return true;
}
// right
if (sx < n - 1 && arr[sy][sx + 1] == 0 && right == 0) {
if (findway(arr, sy, sx + 1, 0, 0, 1, 0))
return true;
}
// top
if (sy >= 1 && arr[sy - 1][sx] == 0 && top == 0) {
if (findway(arr, sy - 1, sx, 0, 1, 0, 0))
return true;
}
// bottom
if (sy < n - 1 && arr[sy + 1][sx] == 0 && bot == 0) {
if (findway(arr, sy + 1, sx, 1, 0, 0, 0))
return true;
}
return false;
}
int main()
{
int sy, sx;
cin >> n >> sy >> sx >> dy >> dx;
vector<vector<int>> arr(n);
for (int i = 0; i < n; ++i) {
arr[i].resize(n);
for (int j = 0; j < n; ++j)
cin >> arr[i][j];
}
if (!findway(arr, sy - 1, sx - 1))
cout << "NO";
else cout << "YES";
return 0;
}
Và khi submit, căn bản code vẫn chạy được nhưng lại bị lỗi bộ nhớ ở test 10: Memory limit exceed on test 10 và IDEone cũng báo Time limit exceed với test dưới.
Và đây là test 10:
5 1 1 5 5
1 0 0 0 0
1 1 1 0 0
0 0 0 0 1
0 1 1 1 1
0 0 0 0 0
Dường như nếu n >= 5 thì bị lỗi bộ nhớ. Mọi người cho mình hỏi khắc phục lỗi này như thế nào ạ?
P/S: Mình chưa quan trọng việc tìm lời giải khác mà nguyên nhân của lỗi này trước ạ!
Để cải thiện về mem thì phải truyền tham chiếu cho vector và thu lại hàm còn 4 tham số.
Bởi vì để yên vậy thì mỗi lần truyền thì phải dựng thêm vector rồi copy qua, và đó là thao tác thừa.
Mình đã thử truyền tham chiếu cho vector rồi nhưng vẫn bị lỗi
Memory limit exceed on test 10bạn!Mình chưa hiểu lắm, thu lại còn 4 tham số bằng cách nào bạn? (vì mình thấy tham số arr, sy, sx, top, bot, left, right là nhất thiết phải có rồi?)
nếu được thì em bỏ đệ quy xài 1 cái stack đi.
tránh nhích ngược nhưng ko tránh đi vòng được.
1 0 0 0 0
1 1 1 0 0
0 0 0 0 1
0 1 1 1 1
0 0 0 0 0
chắc bị đi 1 vòng quanh 4 số 0 này rồi nên dẫn tới đệ quy vô tận, tràn stack hay hết memory gì đó
mỗi lần đi tới 1 ô thì mark nó là đi rồi bằng 1 số khác 0 là được, ví dụ mark nó số 2 chẳng hạn, hoặc số tăng dần cũng được nếu có ko quá 2 tỉ ô
1 2 3 4 5
1 1 1 7 6
0 0 0 0 1
0 1 1 1 1
0 0 0 0 0
lúc tới số 7 nó ko trèo lên ô số 4 nữa vì ô đó khác 0 ko đi được, tránh đi thành vòng
Kết hợp với việc đánh dấu những ô đã đi qua thì ta chỉ cần một mảng trạng thái duy nhất (cái vector) vì vẫn có thể trả về trạng thái trước khi gọi còn 4 tham số là vì bạn chỉ đi có một bước nên chỉ có một tham số khác 0 => thay bằng 1 enum.
Khi đó lời gọi đệ quy có dạng:
findway(arr, 2, 3, UP);với UP là 1 hằng trong enum. Thay vì phang 4 cái
const intthì ghi enum 4 hướng cho nhanh.Bạn thử đọc qua về thuật toán DFS xem. Khá đơn giản thôi mà hay áp dụng vào mấy bài tìm đường đi
Đệ quy ntn là DFS rồi. Cái stack là chi tiết cài đặt thôi, mà depth cao lắm cũng chỉ 81.
Mình thì hay dùng queue kèm 1 mảng là map và 1 mảng là đường đi thấy nó gọn lắm chẳng cần đến đệ qui. Chắc cũng tương tự thế này thôi :v
Dùng queue là BFS, đâu phải DFS
Ờ nhỉ, em khờ quá, tự nhiên đi qua ô đó mà ko mark là đã đi rồi thì bị lặp
Code đã AC!
Mình chỉ đang tìm hiểu các thuật toán thông dụng để đi thi HSG như nhánh cận, tham lam, QHĐ cho nhuần thôi chứ chưa đủ trình học tới đồ thị được bạn
DFS chỉ là dùng stack riêng thôi bạn tự nghiên cứu cách thao tác cũng được. Nhưng tìm kiếm sâu dần hay dùng hơn.
BFS thì đụng tới queue khó hơn hai cái này thì đồ thị có thể không cần tường minh.
DFS ăn mem cỡ O(gốc cây) còn BFS ăn mem cỡ O(|cây|).