Cam thối trong C++

Giới thiệu

Cho một lưới (grid) mà mỗi ô có thể là:

0: ô trống
1: cam tươi
2: cam thối

Mỗi phút, cam tươi liền kề (trên, dưới, trái, phải) với cam thối sẽ trở thành cam thối. Tìm số phút tối thiểu cho đến khi không còn cam tươi nào. Trả về -1 nếu không thể.

Ví dụ

Đầu vào: [[2,1,1],[1,1,0],[0,1,1]] → Đầu ra: 4

Ý tưởng giải thuật (BFS đa nguồn)

Cách tiếp cận tối ưu sử dụng hàng đợi (BFS) từ tất cả cam thối ban đầu:

Đưa tất cả vị trí cam thối (giá trị 2) vào hàng đợi.
Đếm số cam tươi ban đầu.
Thực hiện BFS theo từng "lần lượt" (level) tương ứng với mỗi phút:
- Với mỗi cam thối trong hàng đợi, kiểm tra 4 hướng.
- Nếu gặp cam tươi, biến thành cam thối, giảm bộ đếm, thêm vào hàng đợi cho phút sau.
Kết thúc khi hàng đợi rỗng. Trả về số phút nếu không còn cam tươi, ngược lại -1.

Ví dụ triển khai (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        queue<pair<int,int>> q;
        int fresh = 0;
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) q.push({i, j});
                else if (grid[i][j] == 1) fresh++;
            }
        }
        
        if (fresh == 0) return 0;
        
        int minutes = 0;
        vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        
        while (!q.empty()) {
            int sz = q.size();
            bool infected = false;
            while (sz--) {
                auto [x, y] = q.front(); q.pop();
                for (auto [dx, dy] : dirs) {
                    int nx = x + dx, ny = y + dy;
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 1) {
                        grid[nx][ny] = 2;
                        fresh--;
                        q.push({nx, ny});
                        infected = true;
                    }
                }
            }
            if (infected) minutes++;
        }
        
        return fresh == 0 ? minutes : -1;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{2,1,1},{1,1,0},{0,1,1}};
    cout << ob.orangesRotting(v);
    return 0;
}

Đầu vào

{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}