Show problems as
Classic problem #1970HardArrayBinary SearchDepth-First SearchBreadth-First SearchUnion-FindMatrix

Last Day Where You Can Still Cross

Real-world version: Last Day the Flats Stay Walkable
Tracked in this browser only
Read Last Day Where You Can Still Cross on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A tidal flat is laid out as a grid of rows rows and cols columns. Rows are numbered 1 through rows starting at the north jetty, so row 1 runs along the north jetty and row rows runs along the south jetty. Columns are numbered 1 through cols from west to east.

Every square starts dry. Days are numbered from 1, and on day d the square floods[d - 1] = [r, c] goes under water and stays under from then on. The list covers every square of the flat exactly once, so by day rows * cols nothing is dry.

A walk across on a given day starts on any dry square in row 1, ends on any dry square in row rows, and moves from a square to a dry square sharing a side with it, meaning one step north, south, east or west. Diagonal steps are not allowed, and every square on the walk must be dry that day.

Return the largest day number on which a walk across is still possible.

Examples

Example 1

Input
rows = 3, cols = 3, floods = [[2, 2], [1, 1], [3, 3], [1, 3], [3, 1], [2, 1], [2, 3], [1, 2], [3, 2]]
Output
2

On day 2 the flooded squares are (2,2) and (1,1). The route (1,3), (2,3), (3,3) starts in row 1 on the north jetty, steps south twice onto dry squares, and finishes in row 3 on the south jetty. On day 3 the square (3,3) also floods.

Example 2

Input
rows = 2, cols = 3, floods = [[1, 2], [2, 2], [1, 1], [2, 3], [1, 3], [2, 1]]
Output
3

After the first three squares flood, the dry squares are (1,3), (2,1) and (2,3), and the step from (1,3) to (2,3) crosses from the north jetty row to the south jetty row.

Example 3

Input
rows = 4, cols = 4, floods = [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3], [4, 1], [4, 2], [4, 3], [1, 4], [2, 4], [3, 4], [4, 4]]
Output
12

The first twelve days flood columns 1, 2 and 3 completely and leave column 4 untouched, so on day 12 the four squares of column 4 form a walk from the north jetty row to the south jetty row. Column 4 starts flooding on day 13.

Constraints

  • 2 <= rows, cols <= 2 * 10^4
  • 4 <= rows * cols <= 2 * 10^4
  • floods.length == rows * cols
  • floods[i].length == 2
  • 1 <= floods[i][j] <= 2 * 10^4
  • Each floods[i] is [r, c] with 1 <= r <= rows and 1 <= c <= cols, and no square is listed twice.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def last_dry_day(rows: int, cols: int, floods: list[list[int]]) -> int:
Java
public int lastDryDay(int rows, int cols, int[][] floods)

More on the same topics