Count Traversable Mazes
National Olympiad — National round (2014 season)
Submission name: mazes.cpp
Problem summary
Count m×n binary mazes whose top and bottom rows are black. A route may enter any white cell on the west boundary and leave through the east, moving only north, south and east. Count traversable mazes modulo 1234567.
Input
Two integers m n.
Output
The number of traversable mazes modulo 1234567.
Constraints
3≤m≤7; 3≤n≤10^18.
Worked example
An independently prepared example for this explanation.
Input
4 3
Output
17
Solution analysis
- Only h=m−2 interior rows vary. After processing a column, record a bitmask of its white cells reachable from the west. There are at most 2^5=32 states.
- For a new white-cell mask W, find its consecutive vertical runs. A whole run becomes reachable precisely when it intersects the previous reachable mask; eastward entry at that intersection then allows vertical movement throughout the run. Count every W as one transition, including different W values that lead to the same reachable mask.
- Pretend that all interior rows are reachable immediately west of the first column. Applying n transitions then summing nonempty final states counts exactly successful mazes. Exponentiate the small transition matrix by repeated squaring for huge n. For m=4,n=3, the result is 17.
Why it works
Any route into a column enters eastward from a previously reachable row and stays within one vertical white run. Thus the run-intersection transition computes precisely all reachable cells. Induction proves the state interpretation after every column. Each maze is one sequence of white masks, counted once by matrix multiplication; a nonempty last state is equivalent to an exit route.
Watch out. Track reachable cells, not just which cells are white. Keep zero as a dead state, count transition multiplicities, and use 64-bit intermediate modular products.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
// Algorithm: Only h=m−2 interior rows vary.
using namespace std;
const long long modulo=1234567;
using Matrix=vector<vector<long long>>;
Matrix multiply(const Matrix&a,const Matrix&b){
int size=static_cast<int>(a.size());
Matrix result(size,vector<long long>(size,0));
for(int i=0;i<size;i++){
for(int k=0;k<size;k++){
if(a[i][k]!=0){
for(int j=0;j<size;j++){
result[i][j]=(result[i][j]+a[i][k]*b[k][j])%modulo;
}
}
}
}
return result;
}
int main(){
int rows;
long long columns;
cin>>rows>>columns;
int height=rows-2;
int states=1<<height;
Matrix transition(states,vector<long long>(states,0));
for(int previous=0;previous<states;previous++){
for(int white=0;white<states;white++){
int reachable=0;
int row=0;
while(row<height){
if((white&(1<<row))==0){
row++;
continue;
}
int run=0;
while(row<height&&(white&(1<<row))!=0){
run|=1<<row;
row++;
}
if((run&previous)!=0){
reachable|=run;
}
}
transition[previous][reachable]++;
}
}
Matrix power(states,vector<long long>(states,0));
for(int state=0;state<states;state++){
power[state][state]=1;
}
while(columns>0){
if(columns%2!=0){
power=multiply(power,transition);
}
columns/=2;
if(columns>0){
transition=multiply(transition,transition);
}
}
long long answer=0;
for(int state=1;state<states;state++){
answer=(answer+power[states-1][state])%modulo;
}
cout<<answer<<'\n';
}