The Ninja
National Olympiad — National round
Submission name: ninjata.cpp
Problem summary
An N×N grid has lamps initially off (0) or on (1) at second 1. Unoccupied rooms toggle every second. Begin in the top-left at second 1; this initial entry counts as one second. Move only down or right in one second and enter only rooms dark at arrival. The occupied room stays dark while you wait there for any number of seconds. Find the earliest arrival at the bottom-right.
Input
N, then N rows of N binary values describing second 1.
Output
The earliest arrival second, including the initial second.
Constraints
2 ≤ N ≤ 14; the initial top-left value is 0.
Worked example
An independently prepared example for this explanation.
Input
2 0 1 0 0
Output
3
Solution analysis
- Store earliest arrival per cell, starting at 1.
- For each down/right neighbour, try arrival t+1. Its lamp is initial XOR ((arrival−1) mod 2).
- If it is on, wait one second first. Update neighbours in row-major order.
Why it works
An earlier arrival never harms future choices because waiting in the current room is always allowed. Each transition picks the earliest dark arrival. All predecessors are processed first in this directed acyclic grid.
Watch out. Check darkness at arrival; movement count alone omits waiting and the initial second.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
int main(){
int n;
cin>>n;
vector<vector<int>>a(n,vector<int>(n)),d(n,vector<int>(n,1000000));
for(auto&r:a){
for(int&x:r){
cin>>x;
}
}
d[0][0]=1;
for(int r=0;r<n;r++){
for(int c=0;c<n;c++){
for(int k=0;k<2;k++){
int rr=r+(k==0),cc=c+(k==1);
if(rr==n||cc==n){
continue;
}
int arrival=d[r][c]+1;
if(a[rr][cc]^((arrival-1)&1)){
arrival++; // Wait if needed.
}
d[rr][cc]=min(d[rr][cc],arrival);
}
}
}
cout<<d[n-1][n-1]<<'\n';
}