ABC151に参加してD問題解けなかった復習としてまとめる
幅優先探索と深さ優先探索
wikiの図がすごいわかりやすいから見て・・・
まぁこんな感じに木があると思って
親A
├子AA
│ ├孫AAA
│ └孫AAB
├子AB
│ └孫ABA
└子AC
├孫ACA
├孫ACB
└孫ACC
幅優先探索
親ノードにぶら下がってる子ノードを全部探索してから、探索した子ノードにぶら下がってる全部の孫ノードを探索する
キューを使って解く
- キューに親Aを入れる ( キューの状態：親A )
- 親Aを取り出す ( キューの状態：空 )
- 親Aにぶら下がってる子AA,AB,ACを全部キューに入れる ( キューの状態：子AA 子AB 子AC )
- 子AAを取り出す ( キューの状態：子AB 子AC )
- 子AAにぶら下がってる孫AAA,AABを全部キューに入れる ( キューの状態：子AB 子AC 孫AAA 孫AAB )
- キューが空っぽになるまで繰り返し
探索する順番は
親A→子AA→子AB→子AC→孫AAA→孫AAB→孫ABA→孫ACA→孫ACB→孫ACC
親→子→孫の順番に探索するのが幅優先探索
深さ優先探索
親ノードから行けるとこまで行ってから、他に孫ノードがないか、また戻って他に子ノードがないか探索する
こっちはスタック使う こっちは先入れ先出し
- スタックに親Aを入れる ( スタックの状態：親A )
- 親Aを取り出す ( スタックの状態：空 )
- 親Aにぶら下がってる子AA,AB,ACをスタックに入れる ( スタックの状態：子AA 子AB 子AC )
- 子ACを取り出す ( スタックの状態：子AA 子AB )
- 子ACにぶら下がってる孫ACA,ACB,ACCをスタックに入れる ( スタックの状態：子AA 子AB 孫ACB 孫ACB 孫ACC )
- スタックが空になるまで繰り返し
探索する順番は
親A→子AC→孫ACC→孫ACB→孫ACA→子AB→孫ABA→子AA→孫AAA→孫AAB
木の図の外周を順番に見てくイメージなんだけど伝われ・・・
スタックを使うとは書いたけど再帰で探索すると深さ優先探索になる（一概にはそうとは言えない？）
解けなかった問題
D - Maze Master
問題文
高橋君は、縦Hマス、横WマスのH×Wマスからなる迷路を持っています。
上からi行目、左からj列目のマス(i,j)は、Sijが'#'のとき壁であり、'.'のとき道です。
道のマスからは、上下左右に隣接する道のマスに移動することができます。
迷路の外に移動すること、壁のマスへ移動すること、斜めに移動することはできません。
高橋君は、道のマスからスタートとゴールを自由に決め、迷路を青木君に渡します。
青木君は、移動回数が最小になるようにしてスタートからゴールまで移動します。
高橋君がスタートとゴールの位置を適切に定めたとき、青木君の移動回数は最大で何回になるでしょうか？
制約
1≤H,W≤20
Sijは'.'か'#'
Sは'.'を2つ以上含む
任意の道のマスから任意の道のマスまで0回以上の移動で到達できる
入力
入力は以下の形式で標準入力から与えられる。
H W
S11...S1W
:
SH1...SHW
回答
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String[] params = in.nextLine().split(" ");
int h = Integer.parseInt(params[0]);
int w = Integer.parseInt(params[1]);
String[][] ss = new String[h][w];
for (int i = 0; i < h; i++) {
params = in.nextLine().split("");
for (int j = 0; j < w; j++) {
ss[i][j] = params[j];
}
}
// 全ての場所をスタート地点として最長距離を回答とする
int maxDistance = 0;
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
maxDistance = Math.max( maxDistance , getMaxDistanceWithBfs( ss , i , j ) );
}
}
System.out.println(maxDistance);
}
/**
* 幅優先探索で最長距離を返す
* @param ss 迷路の配列
* @param startY スタート地点のY座標
* @param startX スタート地点のX座標
* @return 最長距離
*/
private static int getMaxDistanceWithBfs( String[][] ss , int startY , int startX ) {
int[][] distances = new int[ss.length][ss[0].length];
Queue<Integer> queue = new ArrayDeque<>();
// 四方の距離の定義 順に左上右下
int[] dx = { -1 , 0 , 1 , 0 };
int[] dy = { 0 , 1 , 0 , -1 };
int maxDistance = 0;
// スタート位置をキューに追加しておく
queue.add( startX );
queue.add( startY );
// キューが空になった時 = 探索できる場所がなくなった時
// ループ回数 = スタート位置からの距離
while( !queue.isEmpty() ) {
int x = queue.remove();
int y = queue.remove();
// 今いる場所が壁の場合処理しない
if( "#".equals( ss[y][x] ) ){
continue;
}
maxDistance = Math.max( maxDistance , distances[y][x] );
// 四方を確認
for( int i = 0 ; i < 4 ; i++ ){
// 確認先の座標
int xx = x + dx[i];
int yy = y + dy[i];
// 確認先の座標が配列外にいないこと
if( !( 0 <= yy && yy < ss.length && 0 <= xx && xx < ss[0].length ) ) {
continue;
}
// 確認先の座標が壁でないこと
if( !".".equals( ss[yy][xx] ) ) {
continue;
}
// 既に通った道でないこと
if( distances[yy][xx] != 0 ){
continue;
}
// スタート地点でないこと
if( xx == startX && yy == startY ){
continue;
}
queue.add( xx );
queue.add( yy );
distances[yy][xx] = distances[y][x] + 1;
}
}
return maxDistance;
}
}
キューから取り出した座標から四方を確認して、通れる道ならキューに追加
その時に、今いる距離+1を通れる場所に格納するっていう
通ったかどうかの判定配列をスタート地点からの距離を格納しとく配列と一緒にして書いたから
確認先の座標がスタート地点かどうかも見る必要があった
3 5
#####
# ..##
#####
こういう入力だった場合にS22をスタート地点、S23をゴール地点とした回答1が正解なんだけど、
スタート地点からの距離を測っていくと、
#####
# 0.##
#####
#####
# 01##
#####
#####
# 21##
#####
こんな感じにスタート地点（スタート地点からの距離：0）がまだ通ってない判定されて行って戻ってくるのが最長ルートになっちゃう
判定の中にも上記と同じようなのがあったみたいで、チェック外したらちゃんとWAになった
Javaには標準でPointっていう座標クラスがあるからそっち使えばよかったかも
キューにはX→Yの順で追加＋2つずつ追加／取り出しって決めて書いたからいらなかったけど
備考
全座標をスタート地点として総なめするのどうにかならないか？
今回の問題は二次元配列のサイズが最大20×20
座標すべての場所をスタート地点として確認しても実行時間に余裕があった
もっと広くなったら無理か？
同じルートの計算は使いまわせないか？
この書き方より速くなるのか？
他の人の回答いくつか見て回ったけど
この問題としては総なめする必要があるらしい
幅優先探索使った他の問題見てみた方がいいかも
1/13 回答ソース修正
この記事を書くにあたり、最初はこういう風に書いてた
https://atcoder.jp/contests/abc151/submissions/9485696
修正箇所のポイント
自分なりのね
各座標の距離を測る配列を用意することになったからSystem.arraycopyが必要なくなった
// 探索の中で配列を操作するので、コピーを渡す
for( int k = 0 ; k < h ; k++ ){
copy[k] = new String[w];
System.arraycopy( ss[k] , 0 , copy[k] , 0 , w );
}
int distance = getMaxDistanceWithBfs( copy , i , j );
Mathクラス使うようにした
便利だ・・・
int distance = getMaxDistanceWithBfs( copy , i , j );
if (maxDistance < distance) {
maxDistance = distance;
}
キューにX→Yの順で入れるって決めてしまえば座標用クラスいらない
/**
* 座標用クラス
*/
public static class Position {
int x;
int y;
public Position( int x , int y ) {
this.x = x;
this.y = y;
}
}
Queue<Position> queue = new ArrayDeque<>();
queue.add( new Position( startX , startY ) );
ループ処理変えた
return distance - 1;
この帳尻合わせみたいなのほんと嫌い
元々は
- キューが空になるまでループ
- 取り出した距離と同じ距離のものをすべて確認するためにループ
- 四方を確認（なんでfor使わなかった）
っていう3重ループ
各座標の距離を格納しとくための配列を用意したことで、2のループが必要なくなった
2のループは距離を測るのに必要だったけどこいつの所為で最終的にdistance-1する必要があった