Lưới ngập nước
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho một bảng lưới kích thước $N \times M$, ô $(i, j)$ có độ cao là $h_{i,j}$. Tại ngày thứ $t$ ($t \ge 0$), mực nước dâng lên độ cao $t$, khiến tất cả các ô có $h_{i,j} \le t$ bị ngập nước và không thể đi qua. Bạn chỉ có thể di chuyển giữa các ô kề cạnh (trên, dưới, trái, phải) chưa bị ngập (tức có độ cao $> t$).
Hãy tìm giá trị $t$ nhỏ nhất ($t \ge 0$) sao cho tại ngày thứ $t$, không còn đường đi nào từ ô $(1, 1)$ đến ô $(N, M)$ (bao gồm cả trường hợp ô $(1, 1)$ hoặc $(N, M)$ bị ngập).
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N, M \le 500$).
- $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $h_{i,j}$ ($0 \le h_{i,j} \le 10^9$).
Dữ liệu ra
- Một số nguyên duy nhất là ngày $t$ nhỏ nhất không thể đi từ $(1, 1)$ đến $(N, M)$.
Ví dụ
| Input | Output |
|---|---|
| 2 2 3 2 1 4 |
2 |
Giới hạn
- $1 \le N, M \le 500$
- $0 \le h_{i,j} \le 10^9$
Community Discussion