Official
D - Do use hexagon grid Editorial by en_translator
Basically, it is same as counting connected components in a square grid or a graph.
Here is some references in Japanese.
- グラフの連結成分の個数を求めるアルゴリズム (“Algorithm counting the number of connected components”)
- DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 4-2. 連結成分の個数 (DFS (Depth First Search) tutorial! - Introduction to the world of graphs and algorithm - Part II. 4-2. Counting connected components)
- Connect Cities(ABL-C) and Connect Cities Editorial by Mitsubachi
Then, how to handle a hexagonal grid?
A big hint is in the problem statement:
Cell \((i,j)\) is adjacent to the following six cells:
- \((i-1,j-1)\)
- \((i-1,j)\)
- \((i,j-1)\)
- \((i,j+1)\)
- \((i+1,j)\)
- \((i+1,j+1)\)
That is, we just need to implement the adjacency of \(4\) or \(8\) neighbors in the square grid with this.
Note that the coordinates may be negative in this problem. (If you want to treat it as positive number, add an arbitrary constant to \(X_i\) and \(Y_i\).)
Sample code (C++):
#include<bits/stdc++.h>
#include<atcoder/dsu>
using namespace std;
using namespace atcoder;
int mem[2010][2010]={0};
int dx6[6]={-1,-1,0,0,1,1};
int dy6[6]={-1,0,-1,1,0,1};
int main(){
int n;
cin >> n;
dsu uf(n+1);
vector<int> x(n+1),y(n+1);
for(int i=1;i<=n;i++){
cin >> x[i] >> y[i];
x[i]+=1005;y[i]+=1005;
mem[x[i]][y[i]]=i;
}
for(int i=1;i<=n;i++){
for(int k=0;k<6;k++){
int nx=x[i]+dx6[k];
int ny=y[i]+dy6[k];
if(mem[nx][ny]>0){
uf.merge(i,mem[nx][ny]);
}
}
}
int res=0;
for(int i=1;i<=n;i++){
if(uf.leader(i)==i){res++;}
}
cout << res << "\n";
return 0;
}
posted:
last update: