ABC-269 D - Do use hexagon grid 別解説(C++) - 茶処・まっちゃら亭の一休みばしょ

前回の記事とうって変わって真面目な記事です。ご了承ください。
今回は、自分が茶梅しているときに書かれていなかった別解説を書きたいと思います(嘘解法ならごめんなさい...一応ACは確認しております)。

公式解説の説明(ざっくり)

(...というか、現茶が書いていいものなのか...？まあいっか)

公式の解説(physics0523さんの解説)では、 $2010×2010$ の大きさの二次元配列を用いて実装しています。
そして我が家の伝統 +UnionFind+ を使って連結性を判定しながら連結成分をカウントしていく、という感じになっています。

これは $|X_i|,|Y_i|\le 1000$ のみで解けるように感じられます。しかし私が書いた解法(既出そうですが...)では、さらに拡張して $|X_i|,|Y_i|\le 10^{9}$ で解くこともできます。

自分なりに考えた解法

黒いマスは与えられた $(X_i,Y_i)$ のみだけなので、この $N$ 個のマス以外は、基本的に考えなくてもよいです。これは上の解説も同じことをしています。
$4$ 近傍や $6$ 近傍で深さ優先探索(DFS)するのも同じですが、ここから上の解説とは異なります。

上の解説では、グリッドの情報を保存するために二次元配列を使うのに対し、私の解法では map(連想配列) を使って判定しています。

どういうこと？

二次元配列は、黒いマスの座標以外に余分な白いマスの情報も保存されています。しかし map を用いることで、黒いマスの座標以外の情報を持たなくなり、情報量が少なくなります。さらに二次元配列は配列の大きさにとらわれるのに対し、map ではその大きさにとらわれない※のが、この解法の特徴です。

※ これ、set でもよくない...？と思った方もいるでしょう。しかし map の方がいいことを後半の方に説明していますので、ご参照ください。

DFSの方法

通常、グリッド上の探索では以下の $3$ つの鉄則があります。

1: 今探索している座標がグリッド外に出ていないか？
2: 今探索している座標に、何も障害物(すなわち探索できないような壁マス)が置かれていないか？
3: 今探索している座標が既に探索済ではないか？

しかし、今回は上の鉄則は 1,2 だけ無視することが可能です(グリッド外に出たとしても、それは白いマスを探索しているのと同じなため。また白いマスは障害物扱いになるが、白いマスは探索する必要はないため)。

3: の内容ですが、これを満たしていないと探索の無限ループが起きてしまうのは明らかです。今回はこれだけ満たしていればよいです。

問題は「探索済かどうかどうやって判定するか」です。

いったん、制約を見直してみましょう。制約にはこう書かれています。

「 $(X_i,Y_i)$ は相異なる」

この制約は使えそう...！！！となります。つまり、同じ座標のものがない(まああったとしてもあまり影響はない)ので、座標組ごとに番号をつけて管理するのがよいと思われます。これが map を使う理由でもあります。つまり、

$(X_i,Y_i)$ に番号 $i$ を付ける

とするのがよいでしょう(このとき $i$ は 0-indexed,1-indexedどちらでもよいです。私は0-indexedで実装しています)。

「探索済かどうかどうやって判定するか」の問題に戻ります。上の方法で番号付け、別で探索済かどうかを表す配列 $seen$ で管理すればよいです(詳しく実装例をご覧ください)。

また「今探索している座標が黒いマスかどうか」判定するのは、count 関数などを用いるとよいです。

今回書いたコード(C++)

(Submissionはこちら)

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++) //[0,n)
#define srep(i,a,b) for(int i = a; i <= b; i++) //[a,b]
#define all(A) (A).begin(),(A).end()
#define rall(A) (A).rbegin(),(A).rend()
#define pmt(A) next_permutation(all(A))
using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<ll,ll>;
using pq = priority_queue<ll,vector<ll>,greater<ll>>;
const ll inf = 8e18;
const int iinf = (int)1e9;
const int mod9 = 998244353;
const int mod1 = 1000000007;
struct Edge { int to; ll cost; int from; };
bool compe(const Edge &e,const Edge &e2){ return e.cost < e2.cost; }
using Graph = vector<vector<int>>;
using SGraph = vector<set<ll>>;
template <typename T>
ll siz(T& a){return (ll)a.size();}

int main(void){
    int n; cin >> n;
    map<P,int> mp;
    vector<P> p(n);
    rep(i,n){
        int x,y; cin >> x >> y;
        mp[{y,x}] = i;
        p[i] = {y,x};
    }

    int ans = 0;
    vector<int> seen(n,0);
    stack<P> st;
    rep(i,n){
        if(seen[i]) continue;
        st.push(p[i]);
        while(siz(st)){
            auto state = st.top(); st.pop();
            srep(dy,-1,1){
                srep(dx,-1,1){
                    if(dy*dx == -1) continue;
                    int ny = state.first+dy,nx = state.second+dx;
                    if(!mp.count({ny,nx})) continue;
                    if(seen[mp[{ny,nx}]]) continue;
                    seen[mp[{ny,nx}]] = 1;
                    st.push({ny,nx});
                }
            }
        }
        ans++;
    }
    cout << ans;
}

Epilogue

やっぱ探索問題(特にグラフ)ってこれだから楽しい...！！！！！！