Official
D - Do use hexagon grid Editorial by physics0523
基本的には、正方形グリッドやグラフで連結成分の数を求める問題と同じです。
いくつか日本語の参考記事を挙げます。
- グラフの連結成分の個数を求めるアルゴリズム
- DFS (深さ優先探索) 超入門! 〜 グラフ・アルゴリズムの世界への入口 〜【後編】 4-2. 連結成分の個数
- Connect Cities(ABL-C) および Connect Cities 解説 by Mitsubachi
では、六角形のグリッドの場合はどう対応すればよいでしょうか?
実は、問題文に大きなヒントがあります。
マス \((i,j)\) は以下の \(6\) つのマスと隣接します。
- \((i−1,j−1)\)
- \((i−1,j)\)
- \((i,j−1)\)
- \((i,j+1)\)
- \((i+1,j)\)
- \((i+1,j+1)\)
つまり、正方形のグリッドで用いた \(4\) 近傍や \(8\) 近傍の隣接関係をこちらに換えて同じように実装すればよいのです。
この問題では、座標が負にもなりうることに注意してください。 (正の範囲で取り扱いたい場合は、 \(X_i,Y_i\) に適当な定数を足せばよいです。)
実装例(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: