Official Analysis (C++, Java, and Python)

Explanation

There can be at most $n \cdot m$ rooms, which is about $10^{10}$ total rooms and too much to process. However, not all of them are relevant (i.e. there are some rooms that are not a start point or an end point for a ladder, so processing them would be extraneous). Therefore, coordinate compression can be used here.

We can use shortest paths to solve the problem. Since we can move freely on a floor, we can use Dijkstra's to find the minimal health to reach every room on that floor. Then, we can iterate over all the ladders on that floor and calculate the minimum health to travel to the endpoints of each ladder by using it.

Implementation

Time Complexity: $\mathcal O(n + k\log^2 k)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Ladder {
	int from_row, from_col;
	int to_row, to_col;
	int health;
};