振り返り【D問題】グリッド問題 ABC387 BFS 【灰】C++

[@actorbug-nat]

修正前のソースで、具体的に問題が起こるケースを追いたいなら、以下の入力例はいかがでしょうか。
3 1
.
S
G
こんな感じで動作するのが分かるかと思います。
・最初にqueUDに(1,0)が登録される
・queUDの先頭(1,0)を処理して、queLRに(2,0)と(0,0)が登録される(queUDは空になる)
・queUDが空なので、stateを0から1にする
・queLRの先頭(2,0)を処理するが、左右とも壁なのでqueUDに値が入らない
・queUDが空なので、stateを1から0にする ←ここが問題
・queLRに(0,0)が登録されていて空ではないので、ループ先頭に戻る
・stateが0なので、queUDの先頭を処理しようとするが、queUDが空なのでエラーで落ちる
念のため、私が修正してACとなったソースを載せておきます。
abc387/submissions/61407187

[@DDincrement]

横から失礼します。
willowさんはstateのチェックのときにもqueueが空かチェックを入れているので、最後は
・queUDが空なのでqueueの処理は何もせずstateを1にする
で動作が怪しいながらも偶然正しく処理が続行されると思いますが、いかがでしょう？

[@actorbug-nat]

おっと失礼、前回の途中段階のソースと見間違えていました。
こちらのソースの場合は、'.'のみ通過可能と判定している('G'が通過可能とみなされない)のが原因ですね。

[@WillowLog]

コードありがとうございます！確認してみます！
どの様なケース発生するのか、意図通り動くのかを確認する入力例を作るのは難しいですね😓バグの原因をわかった上でサンプルを作るのか、バグの原因を絞る為のサンプルを幾つかバリエーションを用意しておくのか…。
…テスト用のサンプルを考えてみると、どういう挙動がありえそえなのかを考える練習になる気がしてきました😳

[@DDincrement]

おお、ACおめでとうございます！
queue2つを交互に使う難しい方で完走するとは。
これができるなら、次にグリッドで「最短距離を求めなさい」が来たら本番中のACも狙えそうですね！
あとは「ゴールできるかどうか」もいけるかな？（これはBFSでもDFSでもどっちでもいい）
一応、当日挑戦でのコードで、「この辺あやしいぞ？」って思った箇所を2点挙げておきます。
1つめ、未探索マスかどうかのチェックにkashikaの中身を調べているように見えます。
で、このkashikaをきちんと管理できていれば多分問題ないんですが、ここについでに距離を数字として表示しようとしていたのが悪さをしているように見えます。
というのは、距離が10以上だと、文字数が増えるせいで迷路の壁が全部ずれると思うんですよね。
最後に走らせたときに、10を超えて初めて右移動しようとしたところでバグっていたのは、これが原因じゃないかと思います。
というか、そもそも、探索済かどうかは距離が1e9かどうかを見ることで話が済んでいるので、kashikaをチェックすることに意味はありません……。
2つめ、モード切り替えのif文の中身が怪しそうに見えます。
横方向のqueueが空になっていたら、というif文を縦モードのときもチェックしてませんかね？
これにより、
横queueが空になったので縦モードになりました！
→縦モードのqueueの先頭は上下とも調査不要でした！横queueには何も追加しません！
→横queueが空なのでモード切り替えをします！
→縦queueの中身が残ってるのに横モード開始
という動作をするように見えます。
横queueが空なので、何もせずにまた縦モードに戻って表面的にはバグらなさそうな気もしますが、本当にそうなのかは自信はありません。
何にせよ、このモード切り替えみたいなことをするときは、以下の2つをした方がいいのかなと思います。
今回なら、少なくともどっちかがやってあれば何も問題はなくなるはずです（もちろん両方やるのが最も安全）。
if(今0番モードかどうか&&0番モードから1番モードに切り替える条件)
のように、現在のモードと切り替え条件の両方を確認する。
モード変更を、bit反転ではなく「0番にする」「1番にする」と明示的に書く。

[@WillowLog]

「 . 」と「 G 」を、範囲チェックのif文に入れようとして、分けたif文にする発想が無かったためにKashimaのデータを使って無理やりGのチェックを入れようとしたのは、改めて見ると👀混ぜるな危険でした😇
条件の動作を、また確認してみます！

[@DDincrement]

通過可能マスにいろいろ種類があって大変……だと思うじゃないですか。
実は「壁と違う」を判定すれば一発です。

[@user-jk1mw2yh5d]

D問題、ACおめでとう！しかも queue 2本を連携するとは！この発想はなかった。むずかしい！
例によって、脳筋コード書いときますｗ
公式解説のように、市松模様の i+j の偶奇とか、距離の偶奇で、上下｜左右を指定するかわりに
最初だけ、上下｜左右どちらへ移動するか指定し、以降、上下｜左右を交互に指定するようにしました
```cpp
// いつものおまじない追加してください
int H, W; // bfs の引数手抜きのため global におく
string S[1000];
int INF = 1e9;
int sh, sw; // 開始位置
int gh, gw; // 終了位置
vector dirs{
{{-1, 0}, {1, 0}}, // dirs[0]: 上下に移動
{{0, -1}, {0, 1}} // dirs[1]: 左右に移動
};
int bfs(int si) { // si: 開始位置から 上下|左右 どちらに移動するか
vector dists(H, vector(W, INF)); // 距離を初期設定
dists[sh][sw] = 0; // 開始位置の距離
queue que({{sh, sw, si}}); // 開始位置の情報を初期設定
while (size(que)) { // 終了位置に未達の場合, que が空になり抜ける. 未達 -> 終了位置の距離 INF
// h,w: 移動元の位置
// i: dirs を選択し, 移動元から 上下|左右 どちらに移動か決めるため
// 距離が +1 する毎に 0|1 (上下|左右) が入れ替わるようにする
auto [h, w, i] = que.front(); // 移動元の情報取得
que.pop(); // 移動元の情報削除
if (S[h][w] == 'G') break; // 終了位置で抜ける
int next_dist = dists[h][w] + 1; // 移動先までの距離
int ni = 1 - i; // i=0 -> ni=1, i=1 -> ni=0, 移動先から 上下|左右 どちらに移動か
for (auto [dh, dw] : dirs[i]) { // dirs[0]: 上下, dirs[1]: 左右
int nh = h + dh, nw = w + dw; // nh,nw: 次の位置
if (!(0 H >> W;
for (int i = 0; i < H; i++) cin >> S[i];
for (int h = 0; h < H; h++) // 開始位置 (sh,sw), 終了位置 (gh,gw) を取得
for (int w = 0; w < W; w++) {
if (S[h][w] == 'S') sh = h, sw = w;
if (S[h][w] == 'G') gh = h, gw = w;
}
int dist = min(bfs(0), bfs(1)); // bfs(0): 開始位置から上下に移動, bfs(1): 開始位置から左右に移動
cout

[@WillowLog]

いざという時、解決バリエーションが身を救う💪✨
コードありがとうございます！動かしながら確認してみます！