回答編集履歴
2
115行目から125行目のコードの説明を先頭に載せた
test
CHANGED
|
@@ -1,4 +1,13 @@
|
|
|
1
|
+
115行目から125行目のコードだけ簡単に説明すると、`i`行`j`列のマスの上下左右に`'.'`のマスがあるか探索しています。
|
|
2
|
+
|
|
3
|
+
115行で4回ループしているのは、上下左右の4方向を探索するためです。
|
|
4
|
+
116行目で、実際に上下左右のマスの座標(`ni`行`nj`列)を求めています。
|
|
5
|
+
あとは、枠外ではないか(119行)、`'*'`ではないか(121行)を確かめて、問題なければ`i`行`j`列から`ni`行`nj`列への辺を`HopcroftKarp`に登録します(124行)
|
|
6
|
+
|
|
7
|
+
---
|
|
8
|
+
|
|
9
|
+
ただ、そもそもなぜこのような処理を行っているのかを理解するには、全体の処理を理解する必要があります。
|
|
1
|
-
|
|
10
|
+
こちらの解説の内容を前提とした説明を行うので、事前に読んでください。
|
|
2
11
|
|
|
3
12
|
https://img.atcoder.jp/soundhound2018/editorial.pdf
|
|
4
13
|
|
|
@@ -19,7 +28,7 @@
|
|
|
19
28
|
|
|
20
29
|
`i`行`j`列のマスが市松模様のどちらの色に塗られるかは、`(i + j) % 2`が0か1かで判定できます。
|
|
21
30
|
こちらの判定は114行目で行われており、`i`行`j`列のマスが「右」に属する場合に`continue`して、「左」のマスしか処理しないようにします。
|
|
22
|
-
そして、
|
|
31
|
+
そして、「左」のマス(`i`行`j`列)から、その上下左右のマス(`ni`行`nj`列、「右」に属する)への辺を`HopcroftKarp`に登録しています(124行目の`hk.addedge(left, right);`)。
|
|
23
32
|
|
|
24
33
|
124行目の直前に、以下のような表示を追加すれば、分かりやすいかもしれません。
|
|
25
34
|
```c++
|
1
直接の質問内容が116行目から125行目のコードの説明だったので、場所を追記
test
CHANGED
|
@@ -19,7 +19,7 @@
|
|
|
19
19
|
|
|
20
20
|
`i`行`j`列のマスが市松模様のどちらの色に塗られるかは、`(i + j) % 2`が0か1かで判定できます。
|
|
21
21
|
こちらの判定は114行目で行われており、`i`行`j`列のマスが「右」に属する場合に`continue`して、「左」のマスしか処理しないようにします。
|
|
22
|
-
そして、「左」のマス(`i`行`j`列)から、その上下左右のマス(`ni`行`nj`列、「右」に属する)への辺を`HopcroftKarp`に登録しています(124行目の`hk.addedge(left, right);`)。
|
|
22
|
+
そして、115行目から125行目のコードは、「左」のマス(`i`行`j`列)から、その上下左右のマス(`ni`行`nj`列、「右」に属する)への辺を`HopcroftKarp`に登録しています(124行目の`hk.addedge(left, right);`)。
|
|
23
23
|
|
|
24
24
|
124行目の直前に、以下のような表示を追加すれば、分かりやすいかもしれません。
|
|
25
25
|
```c++
|