Connected Hexagon Grooves
Autumn Tournament (2014)
Submission name: hexagon.cpp
Problem summary
Hexagon rows have lengths3,4,…,k+2,…,4,3. Each tile has a six-bit mask describing openings toward northeast,east,southeast,southwest,west,northwest. Adjacent tiles connect only when both have openings along their common side. Find the largest connected region.
Input
k followed by2k−1 rows of masks in their left-to-right order.
Output
The maximum connected-component size.
Constraints
2 < k < 200; masks are sums of direction bits1,2,4,8,16,32.
Worked example
Original statement sample.
Input
3 16 1 32 1 40 47 32 8 43 21 56 4 4 56 43 2 2 2 1
Output
6
Solution analysis
- Use axial coordinates(r,q): row r has q from max(0,r−k+1) to min(k+1,r+2). This produces the exact required growing then shrinking shape. Its visual horizontal coordinate can be thought of as2q−r, so the six directions have simple fixed coordinate offsets.
- For a direction with bit2^d, its opposite has bit2^((d+3) mod6). Add a connection only if the neighbor exists and both bits are set. One opening alone is not a passage. Scan all tiles and start an iterative DFS at each unvisited tile.
- Each DFS marks its component and counts its tiles; keep the largest count. The sample has21 tiles across rows3,4,5,4,3. Applying the matching-side rule partitions them into regions, the largest containing 6 tiles. An isolated tile still forms a component of size1.
Why it works
A pair of neighboring tiles is traversable exactly when the two facing opening bits are present, so the modeled graph has exactly the physical passages. DFS visits precisely all vertices reachable from its start. Components partition the tiles, and maximizing their counts gives the required region.
Watch out. Do not connect two tiles merely because one points at the other. Opposite direction bits differ by three positions. Rows after the longest row shift their coordinate range. Use iterative DFS to avoid a deep recursive call stack.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
int k;
cin>>k;
int rows=2*k-1;
int width=k+2;
vector<vector<int>>id(rows,vector<int>(width,-1));
vector<int>masks;
vector<pair<int,int>>position;
for(int row=0;row<rows;row++){
for(int q=max(0,row-k+1);q<=min(k+1,row+2);q++){
int mask;
cin>>mask;
id[row][q]=static_cast<int>(masks.size());
masks.push_back(mask);
position.push_back({row,q});
}
}
array<int,6>dr={-1,0,1,1,0,-1};
array<int,6>dq={0,1,1,0,-1,-1};
vector<bool>visited(masks.size(),false);
int largest=0;
for(int start=0;start<static_cast<int>(masks.size());start++){
if(visited[start]){
continue;
}
vector<int>pending{start};
visited[start]=true;
int size=0;
while(!pending.empty()){
int vertex=pending.back();
pending.pop_back();
size++;
auto[row,q]=position[vertex];
for(int direction=0;direction<6;direction++){
int nextRow=row+dr[direction];
int nextQ=q+dq[direction];
if(nextRow<0||nextRow>=rows||nextQ<0||nextQ>=width){
continue;
}
int next=id[nextRow][nextQ];
if(next==-1||visited[next]){
continue;
}
// Both facing openings are necessary for a passage.
int opposite=(direction+3)%6;
if((masks[vertex]&(1<<direction))&&(masks[next]&(1<<opposite))){
visited[next]=true;
pending.push_back(next);
}
}
}
largest=max(largest,size);
}
cout<<largest<<'\n';
}