Ninja in Alternating Rooms
National Olympiad — National round (2012 season)
Submission name: ninja.cpp
Problem summary
A ninja starts in room (0,0) at second 1 of an N×N grid. Lights alternate each second. He may wait safely in his occupied room or move one room right or down in one second, entering only a dark room. Find the earliest arrival at (N−1,N−1).
Input
N, then an N×N matrix of initial light states: 0 dark, 1 lit.
Output
The arrival second, including the initial second spent in (0,0).
Constraints
2≤N≤1500; the initial room is dark.
Worked example
An independently prepared example for this explanation.
Input
4 0 1 1 1 0 1 0 0 1 0 1 1 1 0 1 1
Output
10
Solution analysis
- For each room store its earliest arrival time. The best preceding arrival comes from the room above or to the left; take the smaller, then add one second for the move.
- A room initially marked b is dark at time t exactly when (t−1) mod 2=b. If the tentative arrival has the wrong parity, wait one extra second in the predecessor. Earlier arrival always dominates later arrival because waiting is safe.
- The sample route arrives at seconds 1:(0,0), 2:(0,1), 4:(1,1), 5:(2,1), 6:(2,2), 8:(2,3), 10:(3,3). The missing seconds are safe waits. A single row of DP values is enough.
Why it works
Every arrival comes from above or left. An earliest predecessor can reproduce any later departure by waiting, so no later predecessor arrival is better. Adjusting its arrival-plus-one to the next allowed parity gives the earliest legal transition. Induction in row-major order yields the optimal destination time.
Watch out. Time starts at 1. The occupied room remains dark during waits. Only right and down moves are allowed.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int size;
cin>>size;
const int infinity=1000000000;
vector<int>earliest(size,infinity);
for(int row=0;row<size;row++){
for(int column=0;column<size;column++){
int initialLight;
cin>>initialLight;
if(row==0&&column==0){
earliest[column]=1;
continue;
}
int arrival=earliest[column];
if(column>0){
arrival=min(arrival,earliest[column-1]);
}
arrival++;
// Waiting once changes the destination light parity.
if((arrival-1)%2!=initialLight){
arrival++;
}
earliest[column]=arrival;
}
}
cout<<earliest.back()<<'\n';
}