Conveyor Maze
National Olympiad — Regional round (2021 season)
Submission name: maze.cpp
Problem summary
Each cell of an N×M grid moves you one cell in its arrow direction, possibly outside the grid. For each independent query, change one arrow, start at a specified cell, and report how many distinct cells are visited before exiting, or zero if the walk loops.
Input
N M; N rows of M arrows <,>,v,^; Q; then queries Sx Sy Cx Cy Cd, with one-based coordinates.
Output
For each query, the number of visited cells before exit, or zero for an infinite walk.
Constraints
1 ≤ N,M ≤ 1500; 1 ≤ Q ≤ 100000; all query cells are within the grid.
Worked example
Official example, transcribed with whitespace restored from the PDF.
Input
3 4 >>v> ><v> ^>>^ 4 2 1 1 1 ^ 2 1 2 2 > 2 1 2 1 < 1 1 2 4 ^
Output
0 6 1 8
Solution analysis
- Add an outside vertex 0 with a self-loop. The original arrows form a functional graph: every component consists of a directed cycle with reverse trees feeding its cycle vertices. Remove indegree-zero vertices to identify cycles, then record each cycle’s order and length. Traverse each reverse tree iteratively, recording its cycle root, depth, and Euler entry/exit times.
- These labels answer forward reachability distances in constant time. A noncycle target is reachable precisely when it is an ancestor in the same reverse tree; Euler intervals test this and the depth difference gives its distance. A cycle target is reachable precisely in the same component; add the source’s depth to the modular distance around the cycle. The component of vertex 0 represents escaping walks, and depth is the number of original cells before exit.
- For query start s and changed cell c, first ask whether the original walk reaches c. If not, return the original exit result. Otherwise let w be the new successor of c. If the original walk from w reaches c, the change creates a loop; if w belongs to a nonescaping component it also loops. In the remaining case return dist(s,c)+1+depth(w). For the third sample query, the changed start arrow immediately exits, so the result is one.
Why it works
The cycle-and-tree decomposition contains every functional-graph vertex, and its tree ancestry and cycle order give exactly all possible forward paths and their distances. A changed edge cannot affect the walk before its first visit to c. After using that edge, all subsequent arrows are original until c is visited again. Such a revisit creates a deterministic loop; if c is never revisited, the walk has the original fate of w. In the exiting case the prefix and suffix cannot overlap, since any overlap would lead back to c. Their cell counts therefore add to dist(s,c)+1+depth(w), proving all query answers.
Watch out. Queries are independent. Count the changed cell itself, distinguish cyclic reachability from tree ancestry, and avoid recursive DFS on millions of cells.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The cycle-and-tree decomposition contains every functional-graph vertex, and its tree
// ancestry and cycle order give exactly all possible forward paths and their distances. A changed edge
// cannot affect the walk before its first visit to c.
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int rows,columns;
cin>>rows>>columns;
int total=rows*columns+1;
vector<int>successor(total),head(total,-1),next(total),indegree(total);
auto cell=[&](int row,int column){
if(row<0||row>=rows||column<0||column>=columns){
return 0;
}
return row*columns+column+1;
};
auto destination=[&](int row,int column,char direction){
if(direction=='<'){
--column;
}
else if(direction=='>'){
++column;
}
else if(direction=='^'){
--row;
}
else{
++row;
}
return cell(row,column);
};
for(int r=0;r<rows;++r){
string line;
cin>>line;
for(int c=0;c<columns;++c){
successor[cell(r,c)]=destination(r,c,line[c]);
}
}
for(int v=0;v<total;++v){
int u=successor[v];
next[v]=head[u];
head[u]=v;
++indegree[u];
}
vector<int>work;
work.reserve(total);
for(int v=0;v<total;++v){
if(indegree[v]==0){
work.push_back(v);
}
}
for(size_t i=0;i<work.size();++i){
int u=successor[work[i]];
if(--indegree[u]==0){
work.push_back(u);
}
}
vector<int>root(total,-1),depth(total),entry(total),leave(total);
vector<int>component(total),position(total),cycleLength(total);
for(int start=0;start<total;++start){
if(indegree[start]==0||root[start]!=-1){
continue;
}
int v=start,length=0;
do{
root[v]=v;
component[v]=start;
position[v]=length++;
v=successor[v];
}
while(v!=start);
do{
cycleLength[v]=length;
v=successor[v];
}
while(v!=start);
}
int timer=0;
work.clear();
for(int cycleRoot=0;cycleRoot<total;++cycleRoot){
if(indegree[cycleRoot]==0){
continue;
}
work.push_back(cycleRoot);
while(!work.empty()){
int v=work.back();
work.pop_back();
if(v<0){
leave[-v-1]=timer;
continue;
}
entry[v]=timer++;
work.push_back(-v-1);
for(int child=head[v];child!=-1;child=next[child]){
if(indegree[child]!=0){
continue;
}
root[child]=cycleRoot;
depth[child]=depth[v]+1;
work.push_back(child);
}
}
}
auto distance=[&](int a,int b)->int{
if(indegree[b]==0){
if(root[a]==root[b]&&entry[b]<=entry[a]&&entry[a]<leave[b]){
return depth[a]-depth[b];
}
return -1;
}
int r=root[a];
if(component[r]!=component[b]){
return -1;
}
int length=cycleLength[b];
return depth[a]+(position[b]-position[r]+length)%length;
};
auto escapes=[&](int v){
return component[root[v]]==0;
};
int queries;
cin>>queries;
while(queries--){
int sr,sc,cr,cc;
char direction;
cin>>sr>>sc>>cr>>cc>>direction;
--sr;
--sc;
--cr;
--cc;
int start=cell(sr,sc),changed=cell(cr,cc);
int before=distance(start,changed);
if(before==-1){
cout<<(escapes(start)?depth[start]:0)<<'\n';
continue;
}
int after=destination(cr,cc,direction);
if(distance(after,changed)!=-1||!escapes(after)){
cout<<0<<'\n';
}
else{
cout<<before+1+depth[after]<<'\n';
}
}
}