Cho ma trận grid kích thước m x n chứa các giá trị:
0: Ô trống1: Quả cam tươi2: Quả cam thối
Mỗi phút, bất kỳ quả cam tươi nào nằm cạnh 4 hướng của quả cam thối đều sẽ bị thối theo. Hãy tính số phút tối thiểu để tất cả cam tươi bị thối. Nếu còn quả cam tươi nào không thể bị thối, trả về -1.
Ví dụ 1:
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4Ví dụ 2:
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1Định Dạng Đầu Vào (Input)
Một dòng chứa ma trận 2D grid
Định Dạng Đầu Ra (Output)
Số nguyên là số phút hoặc -1
Ràng Buộc (Constraints)
1 <= m, n <= 10
Ví Dụ Kiểm Thử Mẫu
Ví dụ 1:
Input:
[[2,1,1],[1,1,0],[0,1,1]]
Output:
4
Giải thích: Sau 4 phút
Ví dụ 2:
Input:
[[2,1,1],[0,1,1],[1,0,1]]
Output:
-1
Giải thích: Có quả cam cô lập
Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.
Multi-source BFS O(m * n)
Đẩy toàn bộ quả cam thối (2) ban đầu vào queue. Quét BFS theo từng phút lan ra các ô cam tươi (1).
Dữ liệu đầu vào (Input):
[[2,1,1],[1,1,0],[0,1,1]]
Kết quả kỳ vọng (Expected Output):
4
Dữ liệu đầu vào (Input):
[[2,1,1],[0,1,1],[1,0,1]]
Kết quả kỳ vọng (Expected Output):
-1
Nhập STDIN của bạn (Mỗi dòng một tham số):
Bấm Chạy thử để kiểm tra các bộ test mẫu hoặc Nộp bài để chấm điểm chính thức.
Đang gửi mã và thực thi trên Sandbox Engine...
