質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.49%
C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

459閲覧

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

SmaSTATION

総合スコア29

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2024/02/18 05:53

実現したいこと

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

前提

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

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

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

該当のソースコード

C++

1#include <iostream> 2#include <vector> 3#include <queue> 4#include <algorithm> 5using namespace std; 6 7 8struct HopcroftKarp { 9 int sizeL, sizeR; 10 vector<vector<int> > list; // left to right 11 12 // result 13 vector<bool> seen, matched; 14 vector<int> level, matching; 15 16 // base 17 HopcroftKarp(int l, int r) : sizeL(l), sizeR(r), list(l, vector<int>()) { } 18 inline vector<int>& operator [] (int i) { return list[i]; } 19 inline void addedge(int from, int to) { list[from].push_back(to); } 20 inline friend ostream& operator << (ostream& s, const HopcroftKarp& G) { 21 s << endl; 22 for (int i = 0; i < G.list.size(); ++i) { 23 s << i << " : "; 24 for (int j = 0; j < G.list[i].size(); ++j) { 25 s << G.list[i][j]; 26 if (j + 1 != G.list[i].size()) s << ", "; 27 } 28 s << endl; 29 } 30 return s; 31 } 32 33 // methods 34 void hobfs() { 35 queue<int> que; 36 for (int left = 0; left < sizeL; ++left) { 37 level[left] = -1; 38 if (!matched[left]) { 39 que.push(left); 40 level[left] = 0; 41 } 42 } 43 level[sizeL] = sizeL; 44 while (!que.empty()) { 45 int left = que.front(); 46 que.pop(); 47 for (int i = 0; i < list[left].size(); ++i) { 48 int right = list[left][i]; 49 int next = matching[right]; 50 if (level[next] == -1) { 51 level[next] = level[left] + 1; 52 que.push(next); 53 } 54 } 55 } 56 } 57 bool hodfs(int left) { 58 if (left == sizeL) return true; 59 if (seen[left]) return false; 60 seen[left] = true; 61 for (int i = 0; i < list[left].size(); ++i) { 62 int right = list[left][i]; 63 int next = matching[right]; 64 if (level[next] > level[left] && hodfs(next)) { 65 matching[right] = left; 66 return true; 67 } 68 } 69 return false; 70 } 71 int solve() { 72 seen.assign(sizeL, false); 73 matched.assign(sizeL, false); 74 level.assign(sizeL+1, -1); 75 matching.assign(sizeR, sizeL); 76 int res = 0; 77 while (true) { 78 hobfs(); 79 seen.assign(sizeL, false); 80 bool finished = true; 81 for (int left = 0; left < sizeL; ++left) { 82 if (!matched[left] && hodfs(left)) { 83 matched[left] = true; 84 ++res; 85 finished = false; 86 } 87 } 88 if (finished) break; 89 } 90 return res; 91 } 92}; 93 94const int dx[4] = {1, 0, -1, 0}; 95const int dy[4] = {0, 1, 0, -1}; 96 97int main() { 98 int R, C; cin >> R >> C; 99 vector<string> fi(R); 100 for (int i = 0; i < R; ++i) cin >> fi[i]; 101 102 HopcroftKarp hk(R*C, R*C); 103 int V = R*C; 104 for (int i = 0; i < R; ++i) { 105 for (int j = 0; j < C; ++j) { 106 int left = i * C + j; 107 cout << "left=" << left << endl; 108 cout << "i=" << i << endl; 109 cout << "j=" << j << endl; 110 if (fi[i][j] == '*') { 111 --V; 112 continue; 113 } 114 if ( (i + j) % 2 == 1 ) continue;//隣同士のはすでに見てるから見なくてもいいように? 115 for (int dir = 0; dir < 4; ++dir) { 116 int ni = i + dx[dir], nj = j + dy[dir]; 117 cout << "ni=" << ni << endl; 118 cout << "nj=" << nj << endl; 119 if (ni < 0 || ni >= R || nj < 0 || nj >= C) continue; 120 cout << "fi[ni][nj]=" << fi[ni][nj] << endl; 121 if (fi[ni][nj] == '*') continue; 122 int right = ni * C + nj; 123 cout << "right=" << right << endl; 124 hk.addedge(left, right); 125 } 126 } 127 } 128 auto res = hk.solve(); 129 cout << V - res << endl; 130} 131

試したこと

  • 入力データの入れ替え

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

  • leftとrightの可視化

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

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

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

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

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


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

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

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

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

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

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

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

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

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

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

c++

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

投稿2024/02/18 08:27

編集2024/02/18 13:08
actorbug

総合スコア2224

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

SmaSTATION

2024/02/20 23:33

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.49%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問