Let $ n $ be the number of floors and $ m $ the number of rooms per floor. The building is modeled as a grid with $ n $ rows (floors, indexed top to bottom: floor $ 0 $ is top, floor $ n-1 $ is ground) and $ m+2 $ columns (left stair, $ m $ rooms, right stair). Each cell $ (i, j) $, for $ i \in \{0, \dots, n-1\} $, $ j \in \{0, \dots, m+1\} $, holds a binary value: 1 if the light is on, 0 if off. The first and last columns ($ j=0 $ and $ j=m+1 $) are stairs and always 0.
Define $ L_i = \min\{ j \in \{1, \dots, m\} \mid \text{light at } (i,j) = 1 \} $ if any light is on on floor $ i $, else $ \infty $,
and $ R_i = \max\{ j \in \{1, \dots, m\} \mid \text{light at } (i,j) = 1 \} $ if any light is on on floor $ i $, else $ -\infty $.
Let $ k = \max\{ i \in \{0, \dots, n-1\} \mid L_i \neq \infty \} $ be the highest floor (lowest index) with at least one light on.
Sagheer starts at $ (n-1, 0) $ (ground floor, left stair). He must visit every floor $ i \in \{0, \dots, k\} $ that has at least one light on, in order from bottom to top (i.e., from floor $ n-1 $ up to floor $ k $), and on each such floor $ i $, he must traverse from his entry point (left or right stair) to the leftmost and rightmost lit room on that floor, and then proceed upward.
On floor $ i $, if he enters at left stair ($ j=0 $), the cost to cover all lit rooms is $ R_i - 0 $, and he exits at right stair.
If he enters at right stair ($ j=m+1 $), the cost is $ (m+1) - L_i $, and he exits at left stair.
He may choose, for each floor $ i \in \{0, \dots, k\} $, whether to enter from left or right, but his entry point on floor $ i $ must match the exit point from floor $ i+1 $, since he moves vertically between stairs.
Let $ dp[i][e] $ be the minimum time to turn off all lights on floors $ i $ to $ k $, starting at floor $ i $ at stair $ e \in \{0, 1\} $ (0 = left, 1 = right), having already turned off all lights on floors above $ i $.
Base case:
For $ i = k $:
- $ dp[k][0] = R_k $
- $ dp[k][1] = m+1 - L_k $
Recurrence for $ i < k $:
If floor $ i $ has no lights, then $ dp[i][e] = dp[i+1][e] + 1 $ (just go up one floor).
Otherwise:
- $ dp[i][0] = \min( R_i + 1 + dp[i+1][1],\ (m+1 - L_i) + 1 + dp[i+1][0] ) $
(enter left: go to $ R_i $, then up to next floor’s right; or enter left, go to $ L_i $, then to $ R_i $, then up to next floor’s left — but since he must cover all, and $ L_i \leq R_i $, the path is $ 0 \to R_i $, cost $ R_i $, then up to next floor’s right)
Wait — correction:
Actually, if he enters floor $ i $ at left stair (0), he must go to $ R_i $ to cover all lights (since $ L_i \leq R_i $, and he must visit both ends), so path: $ 0 \to R_i $, cost $ R_i $, then he exits at right stair.
Similarly, if he enters at right stair (1), he goes to $ L_i $, cost $ (m+1) - L_i $, exits at left stair.
So for floor $ i $ with lights:
- If entering at left: cost = $ R_i $, exit at right
- If entering at right: cost = $ m+1 - L_i $, exit at left
Then he moves up one floor: cost 1, to the corresponding stair on floor $ i+1 $.
Thus:
For $ i \in \{0, \dots, k-1\} $:
- If floor $ i $ has lights:
$ dp[i][0] = R_i + 1 + dp[i+1][1] $
$ dp[i][1] = (m+1 - L_i) + 1 + dp[i+1][0] $
- If floor $ i $ has no lights:
$ dp[i][0] = 1 + dp[i+1][0] $
$ dp[i][1] = 1 + dp[i+1][1] $
But Sagheer starts at $ (n-1, 0) $. So we must compute $ dp[n-1][0] $, but only if floor $ n-1 $ has lights. If not, we must go up until we hit the first floor with lights.
Actually, let $ k $ be the highest floor (lowest index) with any light on. Then Sagheer must go from floor $ n-1 $ up to floor $ k $, turning off lights only on floors $ k $ to $ n-1 $.
So define the relevant floors: let $ k $ be the smallest index $ i \in \{0, \dots, n-1\} $ such that $ L_i \neq \infty $. Then Sagheer must visit all floors from $ n-1 $ down to $ k $, i.e., in order: $ n-1, n-2, \dots, k $.
But the problem says: “he will not go upstairs until all lights in the floor he is standing at are off.” So he must finish a floor before going up.
Thus, he starts at floor $ n-1 $. He must turn off all lights on floor $ n-1 $, then go to floor $ n-2 $, etc., up to floor $ k $.
So we process floors from bottom to top: $ i = n-1, n-2, \dots, k $.
Let $ dp[i][e] $ = minimum time to turn off all lights on floors $ i $ to $ n-1 $, starting at floor $ i $ at stair $ e \in \{0,1\} $, and ending at the exit stair on floor $ i $.
Then, for $ i = n-1 $:
- If lights exist:
$ dp[n-1][0] = R_{n-1} $
$ dp[n-1][1] = m+1 - L_{n-1} $
- Else:
$ dp[n-1][0] = 0 $
$ dp[n-1][1] = 0 $
For $ i $ from $ n-2 $ down to $ k $:
If floor $ i $ has lights:
- $ dp[i][0] = R_i + 1 + dp[i+1][1] $
- $ dp[i][1] = (m+1 - L_i) + 1 + dp[i+1][0] $
If floor $ i $ has no lights:
- $ dp[i][0] = 1 + dp[i+1][0] $
- $ dp[i][1] = 1 + dp[i+1][1] $
But if there are no lights on floor $ i $, he just walks from his entry stair to the next floor’s same stair? No — he must go up, but he can choose to go up from either stair? No — he enters floor $ i $ at stair $ e $, and since there are no lights, he just goes up from that same stair to floor $ i+1 $’s same stair. So cost is 1 (to go up), and he exits at same stair on floor $ i+1 $.
But wait — he is going **up** from floor $ i $ to floor $ i+1 $. But we are iterating from bottom up: floor $ n-1 $ is bottom. So when we are at floor $ i $, we are processing it before floor $ i+1 $ (which is above). But in our DP, we go from $ i = n-2 $ down to $ k $, and use $ dp[i+1] $, which is the floor above.
Actually, we are going from bottom to top in physical space, but DP is computed bottom-up: we start at bottom floor, then move to floor above it, etc.
So the recurrence is correct.
But Sagheer starts at $ (n-1, 0) $. So the answer is $ dp[n-1][0] $, but only if floor $ n-1 $ has lights. If not, he must go up.
Actually, we need to find the lowest floor $ k $ with any light on. Then Sagheer must go from floor $ n-1 $ to floor $ k $, turning off lights only on floors from $ k $ to $ n-1 $.
So we can define $ k = \min \{ i \in \{0, \dots, n-1\} \mid \exists j \in \{1,\dots,m\}, \text{light}(i,j)=1 \} $
If no such $ k $, return 0.
Then, we compute $ dp[i][e] $ for $ i = k, k+1, \dots, n-1 $, in reverse order (from $ n-1 $ down to $ k $).
But we must account for the cost of ascending from floor $ n-1 $ to floor $ k $, if $ k < n-1 $. That is, if there are empty floors above $ k $, he must walk up through them.
So we should compute $ dp[i][e] $ for all floors $ i \in \{k, k+1, \dots, n-1\} $, and start from $ i = n-1 $.
Define for $ i \in \{k, k+1, \dots, n-1\} $:
- If $ i = n-1 $:
- If floor $ n-1 $ has lights:
$ dp[n-1][0] = R_{n-1} $
$ dp[n-1][1] = m+1 - L_{n-1} $
- Else:
$ dp[n-1][0] = 0 $
$ dp[n-1][1] = 0 $
- For $ i $ from $ n-2 $ down to $ k $:
- If floor $ i $ has lights:
$ dp[i][0] = R_i + 1 + dp[i+1][1] $
$ dp[i][1] = (m+1 - L_i) + 1 + dp[i+1][0] $
- Else:
$ dp[i][0] = 1 + dp[i+1][0] $
$ dp[i][1] = 1 + dp[i+1][1] $
Then, since Sagheer starts at $ (n-1, 0) $, the answer is $ dp[n-1][0] $.
But wait — if floor $ n-1 $ has no lights, then $ dp[n-1][0] = 0 $, but he still needs to go up to floor $ k $, which is above? No — $ k $ is the topmost floor with lights, and he starts at bottom. So if $ k < n-1 $, then $ k $ is above $ n-1 $? No — floors are indexed 0 (top) to $ n-1 $ (bottom). So $ k $ is the smallest index (highest floor) with lights. So he starts at floor $ n-1 $ (bottom), and must go **up** to floor $ k $ (which is numerically smaller index).
So the path is: start at $ (n-1, 0) $, go up to $ (n-2, 0) $, then $ (n-3, 0) $, ..., until $ (k, 0) $, then traverse floor $ k $, then go up? No — he must turn off lights on each floor before going up. So he must traverse floor $ n-1 $, then go up to $ n-2 $, traverse it, etc., up to floor $ k $.
So the DP above is correct: we start at the bottom floor $ n-1 $, and move upward to $ k $.
Thus, the answer is $ dp[n-1][0] $, computed as above.
But note: if floor $ i $ has no lights, he just goes up from his current stair to the same stair on the floor above. So the DP correctly adds 1 minute to go up.
Final formal statement:
Let $ n, m \in \mathbb{N} $, $ 1 \leq n \leq 15 $, $ 1 \leq m \leq 100 $.
Let $ B \in \{0,1\}^{n \times (m+2)} $, where $ B[i][0] = B[i][m+1] = 0 $ for all $ i $, and $ B[i][j] \in \{0,1\} $ for $ j \in \{1,\dots,m\} $.
Let $ k = \min \{ i \in \{0,\dots,n-1\} \mid \exists j \in \{1,\dots,m\}, B[i][j] = 1 \} $. If no such $ i $, return 0.
For each floor $ i \in \{0,\dots,n-1\} $, define:
- $ L_i = \min \{ j \in \{1,\dots,m\} \mid B[i][j] = 1 \} $ if $ \exists j $ with $ B[i][j] = 1 $, else $ \infty $
- $ R_i = \max \{ j \in \{1,\dots,m\} \mid B[i][j] = 1 \} $ if $ \exists j $ with $ B[i][j] = 1 $, else $ -\infty $
Define $ dp[i][e] $ for $ i \in \{k, k+1, \dots, n-1\} $, $ e \in \{0,1\} $:
- $ dp[n-1][0] = \begin{cases} R_{n-1} & \text{if } L_{n-1} \neq \infty \\ 0 & \text{otherwise} \end{cases} $
- $ dp[n-1][1] = \begin{cases} m+1 - L_{n-1} & \text{if } L_{n-1} \neq \infty \\ 0 & \text{otherwise} \end{cases} $
For $ i $ from $ n-2 $ down to $ k $:
- If $ L_i \neq \infty $:
$ dp[i][0] = R_i + 1 + dp[i+1][1] $
$ dp[i][1] = (m+1 - L_i) + 1 + dp[i+1][0] $
- Else:
$ dp[i][0] = 1 + dp[i+1][0] $
$ dp[i][1] = 1 + dp[i+1][1] $
Answer: $ dp[n-1][0] $
Note: Since Sagheer starts at left stair of ground floor (floor $ n-1 $), we use $ e=0 $.