Robot Reachability
National Olympiad — Regional round
Submission name: robot.cpp
Problem summary
An m-by-n grid is numbered 1…mn in row-major order. Starting at cell r, a robot moves to a vertically or horizontally adjacent cell each move. Sum the labels of all distinct cells it can occupy after exactly k moves.
Input
m n r k.
Output
The sum of reachable cell labels.
Constraints
1 < m,n < 100; 0 < k < 200; r is a valid cell label.
Worked example
An independently prepared example for this explanation.
Input
2 3 1 2
Output
9
Solution analysis
- Compute the Manhattan distance d from the start to each cell.
- Include a cell if d≤k and k−d is even.
Why it works
Every grid move flips checkerboard parity and no path is shorter than Manhattan distance. Conversely a shortest path can be extended by two moves by traversing any incident edge and returning; all cells have neighbors because both dimensions exceed one.
Watch out. Exactly k differs from at most k; count each destination once.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every grid move flips checkerboard parity and no path is shorter than Manhattan distance.
// Conversely a shortest path can be extended by two moves by traversing any incident edge and
// returning; all cells have neighbors because both dimensions exceed one.
#include<iostream>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<iterator>
using namespace std;
int main(){
int m,n,r,k;
cin>>m>>n>>r>>k;
int x=(r-1)/n,y=(r-1)%n;
long long ans=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int d=abs(i-x)+abs(j-y);
if(d<=k&&(k-d)%2==0){
ans+=i*n+j+1;
}
}
}
cout<<ans<<'\n';
}