回答編集履歴

2

115行目から125行目のコードの説明を先頭に載せた

2024/02/18 13:08

投稿

actorbug
actorbug

スコア2433

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
- そして、115行目から125行目のコードは、「左」のマス(`i`行`j`列)から、その上下左右のマス(`ni`行`nj`列、「右」に属する)への辺を`HopcroftKarp`に登録しています(124行目の`hk.addedge(left, right);`)。
31
+ そして、「左」のマス(`i`行`j`列)から、その上下左右のマス(`ni`行`nj`列、「右」に属する)への辺を`HopcroftKarp`に登録しています(124行目の`hk.addedge(left, right);`)。
23
32
 
24
33
  124行目の直前に、以下のような表示を追加すれば、分かりやすいかもしれません。
25
34
  ```c++

1

直接の質問内容が116行目から125行目のコードの説明だったので、場所を追記

2024/02/18 09:30

投稿

actorbug
actorbug

スコア2433

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++