Escaping a Huge Sparse Grid
National Olympiad — National round (2023 season)
Submission name: escape.cpp
Problem summary
Determine four-neighbour reachability from(1,1) to(N,N) in a huge square grid with at most1000 blocked cells, including possible duplicate coordinates.
Input
N M and M blocked coordinate pairs.
Output
YES or NO.
Constraints
2≤N≤100000;0≤M≤min(N²−2,1000); endpoints are safe.
Worked example
Input and output for the worked example discussed below.
Input
4 5 1 3 2 3 3 1 3 2 4 3
Output
NO
Solution analysis
- Retain1,N and every obstacle’s x and y coordinates with their in-bounds neighbours±1. Sort and deduplicate both axis lists.
- Their Cartesian product contains at most(3M+2)² compressed cells. Mark the obstacles at their compressed coordinates and run ordinary four-neighbour BFS. A compressed step may span a large empty strip.
- No obstacle coordinate is skipped inside a strip, while±1 coordinates preserve narrow channels and turns around obstacles. Thus compression preserves reachability, though not original distance. The sample’s blocked barrier prevents reaching the far corner.
Why it works
Each compressed edge expands to a clear straight path because all obstacle coordinates were retained. Conversely an original path can be shortened inside empty coordinate gaps to retained coordinates; neighbouring coordinates preserve passage around blocked cells. Therefore BFS on the compression decides the same reachability.
Watch out. Include adjacent coordinates and boundaries, not only obstacle coordinates. Deduplicate. Do not claim compressed BFS distances equal original lengths.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<utility>
#include<algorithm>
using namespace std;
// Each compressed edge expands to a clear straight path because all obstacle coordinates were retained.
int main(){
int n,m;
cin>>n>>m;
vector<pair<int,int>>blocked(m);
vector<int>xs={1,n},ys={1,n};
for(auto&[x,y]:blocked){
cin>>x>>y;
for(int d=-1;d<=1;d++){
if(x+d>=1&&x+d<=n){
xs.push_back(x+d);
}
if(y+d>=1&&y+d<=n){
ys.push_back(y+d);
}
}
}
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());
sort(ys.begin(),ys.end());
ys.erase(unique(ys.begin(),ys.end()),ys.end());
int rows=xs.size(),cols=ys.size();
vector<unsigned char>state(rows*cols,0);
for(auto[x,y]:blocked){
int r=lower_bound(xs.begin(),xs.end(),x)-xs.begin(),
c=lower_bound(ys.begin(),ys.end(),y)-ys.begin();
state[r*cols+c]=1;
}
vector<int>pending;
pending.reserve(rows*cols);
pending.push_back(0);
state[0]=2;
int dr[4]={-1,1,0,0},dc[4]={0,0,-1,1};
for(size_t head=0;head<pending.size();head++){
int vertex=pending[head];
if(vertex==rows*cols-1){
cout<<"YES\n";
return 0;
}
int r=vertex/cols,c=vertex%cols;
for(int d=0;d<4;d++){
int nr=r+dr[d],nc=c+dc[d];
if(nr>=0&&nr<rows&&nc>=0&&nc<cols){
int next=nr*cols+nc;
if(state[next]==0){
state[next]=2;
pending.push_back(next);
}
}
}
}
cout<<"NO\n";
}