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 ạ!
và thu lại hàm còn 4 tham số.
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.
hai cái này thì đồ thị có thể không cần tường minh.
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?