Lưới ngập nước

Binary-search Buổi 78 — Bế giảng Graphs
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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$
Draft saved