BFS — duyệt theo chiều rộng

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> kq;
        if (root == nullptr) return kq;      // cây rỗng: đừng quên!

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int sz = q.size();               // CHỐT số nút của tầng này
            vector<int> tang;
            for (int i = 0; i < sz; i++) {   // lấy đúng sz nút, không hơn
                TreeNode* u = q.front();
                q.pop();
                tang.push_back(u->val);
                if (u->left)  q.push(u->left);
                if (u->right) q.push(u->right);
            }
            kq.push_back(tang);
        }
        return kq;
    }
};

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if root is None:                     # cây rỗng: đừng quên!
            return []

        kq = []
        q = deque([root])
        while q:
            sz = len(q)                      # CHỐT số nút của tầng này
            tang = []
            for _ in range(sz):              # lấy đúng sz nút, không hơn
                u = q.popleft()
                tang.append(u.val)
                if u.left:
                    q.append(u.left)
                if u.right:
                    q.append(u.right)
            kq.append(tang)
        return kq

class Solution {
public:
    int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
        int n = grid.size();
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return -1;

        queue<pair<int, int>> q;
        q.push({0, 0});
        grid[0][0] = 1;                      // đánh dấu KHI ĐƯA VÀO
        int d = 1;                           // độ dài tính theo số ô

        while (!q.empty()) {
            int sz = q.size();               // một lượt = một tầng khoảng cách
            for (int i = 0; i < sz; i++) {
                auto [r, c] = q.front();
                q.pop();
                if (r == n - 1 && c == n - 1) return d;   // tới đích: d là ngắn nhất

                for (int dr = -1; dr <= 1; dr++)
                    for (int dc = -1; dc <= 1; dc++) {
                        if (dr == 0 && dc == 0) continue;
                        int nr = r + dr, nc = c + dc;
                        if (nr < 0 || nc < 0 || nr >= n || nc >= n) continue;
                        if (grid[nr][nc] != 0) continue;  // tường hoặc đã thăm
                        grid[nr][nc] = 1;                 // đánh dấu NGAY
                        q.push({nr, nc});
                    }
            }
            d++;
        }
        return -1;                           // hàng đợi cạn mà chưa tới đích
    }
};

class Solution:
    def shortestPathBinaryMatrix(self, grid: List[List[int]]) -> int:
        n = len(grid)
        if grid[0][0] == 1 or grid[n - 1][n - 1] == 1:
            return -1

        q = deque([(0, 0)])
        grid[0][0] = 1                       # đánh dấu KHI ĐƯA VÀO
        d = 1                                # độ dài tính theo số ô

        while q:
            for _ in range(len(q)):          # một lượt = một tầng khoảng cách
                r, c = q.popleft()
                if r == n - 1 and c == n - 1:
                    return d                 # tới đích: d là ngắn nhất

                for dr in (-1, 0, 1):
                    for dc in (-1, 0, 1):
                        if dr == 0 and dc == 0:
                            continue
                        nr, nc = r + dr, c + dc
                        if not (0 <= nr < n and 0 <= nc < n):
                            continue
                        if grid[nr][nc] != 0:  # tường hoặc đã thăm
                            continue
                        grid[nr][nc] = 1       # đánh dấu NGAY
                        q.append((nr, nc))
            d += 1
        return -1                            # hàng đợi cạn mà chưa tới đích

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size(), tuoi = 0;
        queue<pair<int, int>> q;

        // ĐA NGUỒN: đưa MỌI quả cam thối ban đầu vào hàng đợi cùng lúc
        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) tuoi++;
            }

        int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1};
        int phut = 0;

        while (!q.empty() && tuoi > 0) {
            int sz = q.size();               // một tầng = một PHÚT
            for (int i = 0; i < sz; i++) {
                auto [r, c] = q.front();
                q.pop();
                for (int k = 0; k < 4; k++) {
                    int nr = r + dr[k], nc = c + dc[k];
                    if (nr < 0 || nc < 0 || nr >= n || nc >= m) continue;
                    if (grid[nr][nc] != 1) continue;   // ô trống hoặc đã thối
                    grid[nr][nc] = 2;                  // thối ngay, khi ĐƯA VÀO
                    tuoi--;
                    q.push({nr, nc});
                }
            }
            phut++;
        }
        return tuoi == 0 ? phut : -1;        // còn cam tươi → không bao giờ thối hết
    }
};

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        q = deque()
        tuoi = 0

        # ĐA NGUỒN: đưa MỌI quả cam thối ban đầu vào hàng đợi cùng lúc
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 2:
                    q.append((i, j))
                elif grid[i][j] == 1:
                    tuoi += 1

        phut = 0
        while q and tuoi > 0:
            for _ in range(len(q)):          # một tầng = một PHÚT
                r, c = q.popleft()
                for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)):
                    nr, nc = r + dr, c + dc
                    if not (0 <= nr < n and 0 <= nc < m):
                        continue
                    if grid[nr][nc] != 1:    # ô trống hoặc đã thối
                        continue
                    grid[nr][nc] = 2         # thối ngay, khi ĐƯA VÀO
                    tuoi -= 1
                    q.append((nr, nc))
            phut += 1

        return phut if tuoi == 0 else -1     # còn cam tươi → không bao giờ thối hết