Untitled

 avatar
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