Untitled
unknown
plain_text
a year ago
2.1 kB
1
Indexable
#include <iostream> // Thư viện nhập xuất cơ bản using namespace std; // Sử dụng không gian tên std const int MAX = 15; // Định nghĩa hằng số tối đa int arr[MAX][MAX]; // Mảng lưu trữ ma trận bool visited[MAX][MAX]; // Mảng lưu trữ các ô đã được duyệt int n, m; // Kích thước ma trận int ans; // Biến lưu trữ kết quả // Hàm giải quyết bài toán đệ quy void solve(int x, int y, int diff) { // Kiểm tra điều kiện thoát của đệ quy if (x < 0 || y < 0 || x >= n || y >= m) { return; } if (arr[x][y] == 3) { ans = min(ans, diff); // Cập nhật kết quả nếu gặp ô mục tiêu return; } visited[x][y] = true; // Đánh dấu ô đã được duyệt // Duyệt các ô xung quanh int up = x - 1; while (arr[up][y] == 0 && up >= 0) { up--; } if (up >= 0 && !visited[up][y]) { solve(up, y, max(diff, x - up)); } int down = x + 1; while (arr[down][y] == 0 && down < n) { down++; } if (down < n && !visited[down][y]) { solve(down, y, max(diff, down - x)); } if (arr[x][y + 1] != 0 && !visited[x][y + 1] && y + 1 < m) { solve(x, y + 1, diff); } if (arr[x][y - 1] != 0 && !visited[x][y - 1] && y - 1 >= 0) { solve(x, y - 1, diff); } visited[x][y] = false; // Hủy đánh dấu ô đã được duyệt } int main() { // Mở file input.txt để đọc dữ liệu freopen("input.txt", "r", stdin); cin >> n >> m; // Nhập kích thước ma trận // Nhập ma trận từ file hoặc bàn phím for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> arr[i][j]; } } // Khởi tạo mảng visited for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { visited[i][j] = false; } } ans = 100; // Khởi tạo kết quả solve(n - 1, 0, 0); // Gọi hàm giải quyết bài toán cout << ans << endl; // In kết quả return 0; }
Editor is loading...
Leave a Comment