プログラムが何をしているのかがわからない。

Question

実現したいこと

この問題のプログラムの116行目から125行目のコードは何を探索をしているのかを知りたいです。
この問題

前提

現在分かっている部分まで状況説明として記します。

• 98行目から114行目までは、入力を受け取りそれぞれの座標においてどの座標が対象になるのかを示す（110行目のif文）
• 16行目の関数で、Hopcraftkarpでグラフ作成する

これらのことは解釈が出来ており、おそらく116行目以降は個々の座標の探索になるのではないかと予想をたてていますが、いまいちよくわかりません。

該当のソースコード

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;


struct HopcroftKarp {
    int sizeL, sizeR;
    vector<vector<int> > list; // left to right
    
    // result
    vector<bool> seen, matched;
    vector<int> level, matching;
    
    // base
    HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector<int>()) { }
    inline vector<int>& operator [] (int i) { return list[i]; }
    inline void addedge(int from, int to) { list[from].push_back(to); }
    inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) {
        s << endl;
        for (int i = 0; i < G.list.size(); ++i) {
            s << i << " : ";
            for (int j = 0; j < G.list[i].size(); ++j) {
                s << G.list[i][j];
                if (j + 1 != G.list[i].size()) s << ", ";
            }
            s << endl;
        }
        return s;
    }
    
    // methods
    void hobfs() {
        queue<int> que;
        for (int left = 0; left < sizeL; ++left) {
            level[left] = -1;
            if (!matched[left]) {
                que.push(left);
                level[left] = 0;
            }
        }
        level[sizeL] = sizeL;
        while (!que.empty()) {
            int left = que.front();
            que.pop();
            for (int i = 0; i < list[left].size(); ++i) {
                int right = list[left][i];
                int next = matching[right];
                if (level[next] == -1) {
                    level[next] = level[left] + 1;
                    que.push(next);
                }
            }
        }
    }
    bool hodfs(int left) {
        if (left == sizeL) return true;
        if (seen[left]) return false;
        seen[left] = true;
        for (int i = 0; i < list[left].size(); ++i) {
            int right = list[left][i];
            int next = matching[right];
            if (level[next] > level[left] && hodfs(next)) {
                matching[right] = left;
                return true;
            }
        }
        return false;
    }
    int solve() {
        seen.assign(sizeL, false);
        matched.assign(sizeL, false);
        level.assign(sizeL+1, -1);
        matching.assign(sizeR, sizeL);
        int res = 0;
        while (true) {
            hobfs();
            seen.assign(sizeL, false);
            bool finished = true;
            for (int left = 0; left < sizeL; ++left) {
                if (!matched[left] && hodfs(left)) {
                    matched[left] = true;
                    ++res;
                    finished = false;
                }
            }
            if (finished) break;
        }
        return res;
    }
};

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int main() {
    int R, C; cin >> R >> C;
    vector<string> fi(R);
    for (int i = 0; i < R; ++i) cin >> fi[i];

    HopcroftKarp hk(R*C, R*C);
    int V = R*C;
    for (int i = 0; i < R; ++i) {
        for (int j = 0; j < C; ++j) {
            int left = i * C + j;
            cout << "left=" << left << endl;
            cout << "i=" << i << endl;
            cout << "j=" << j << endl;
            if (fi[i][j] == '*') {
                --V;
                continue;
            }
            if ( (i + j) % 2 == 1 ) continue;//隣同士のはすでに見てるから見なくてもいいように？
            for (int dir = 0; dir < 4; ++dir) {
                int ni = i + dx[dir], nj = j + dy[dir];
                cout << "ni=" << ni << endl;
                cout << "nj=" << nj << endl;
                if (ni < 0 || ni >= R || nj < 0 || nj >= C) continue;
                cout << "fi[ni][nj]=" << fi[ni][nj] << endl;
                if (fi[ni][nj] == '*') continue;
                int right = ni * C + nj;
                cout << "right=" << right << endl;
                hk.addedge(left, right);
            }
        }
    }
    auto res = hk.solve();
    cout << V - res << endl;
}

試したこと

• 入力データの入れ替え

➔入力データを入れ替えて、fiの読み込んだ結果を見るも入力データとは違うものであった。

• leftとrightの可視化

➔可視化をしてみたものの、これらの指標はすべての探索を終わる合図に使われていると予想した。

補足情報（FW/ツールのバージョンなど）

些細なことでも構いませんので、𠮟咤激励を含めてよろしくお願いいたします。

Answer 1

115行目から125行目のコードだけ簡単に説明すると、i行j列のマスの上下左右に'.'のマスがあるか探索しています。

115行で4回ループしているのは、上下左右の4方向を探索するためです。
116行目で、実際に上下左右のマスの座標(ni行nj列)を求めています。
あとは、枠外ではないか(119行)、'*'ではないか(121行)を確かめて、問題なければi行j列からni行nj列への辺をHopcroftKarpに登録します(124行)

---

ただ、そもそもなぜこのような処理を行っているのかを理解するには、全体の処理を理解する必要があります。
こちらの解説の内容を前提とした説明を行うので、事前に読んでください。

https://img.atcoder.jp/soundhound2018/editorial.pdf

プログラムの流れとしては、以下になります。

1. グリッドグラフを二部グラフとみなしてHopcroftKarpに登録(102～127行)
2. HopcroftKarpから二部グラフの最大マッチングのサイズを得る(128行)
3. (頂点数) - (最大マッチングのサイズ) を求める(129行)

さて、今回の質問は、1.の部分になります。
こちらの肝は、どうやって「グリッドグラフを二部グラフとみなして」いるのか、になります。

解説には、以下のように書かれています。

グリッドを市松模様に塗り分けると、異なる色の間にしか辺が張られないことが分かります

つまり、グリッドを市松模様に塗り分けた際に、片方の色を「左」に、もう片方の色を「右」に属するものとすれば、二部グラフとみなすことができます。

i行j列のマスが市松模様のどちらの色に塗られるかは、(i + j) % 2が0か1かで判定できます。
こちらの判定は114行目で行われており、i行j列のマスが「右」に属する場合にcontinueして、「左」のマスしか処理しないようにします。
そして、「左」のマス(i行j列)から、その上下左右のマス(ni行nj列、「右」に属する)への辺をHopcroftKarpに登録しています(124行目のhk.addedge(left, right);)。

124行目の直前に、以下のような表示を追加すれば、分かりやすいかもしれません。

                cout << "(row: " << i << ", col: " << j << ") -> (row: " << ni << ", col: " << nj << ")" << endl;

Comments

[SmaSTATION]

丁寧なご回答ありがとうございます。該当部分解決しました。
大変助かりました、また機会がありましたら何卒よろしくお願いいたします。