ひとりで勝手にはじめた蟻本読書会 幅優先探索と深さ優先探索 意外と奥が深い全探索 蟻本読書会の続きです。
Contents
迷路の最短路を幅優先探索で探す
迷路の最短路を探すときも幅優先探索を使います。深さ優先探索でもできますが、探索空間 (グラフのサイズ) 自体がとても大きいが、解がスタートから近いところにある場合は幅優先探索が適していると考えられています。
幅優先探索
このページをみると図付きで、幅優先探索を用いた迷路の最短路を探す方法が説明されていますね。
盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。
次に、それぞれのマスが通行可能な空きマス(.)か通行不可能な壁マス(#)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。上記の迷路を解くのに必要な最小移動手数を求めたい。
スタート地点からゴール地点に移動する最小手数を 1 行に出力せよ。入力
R C
sy sx
gy gx
c_1,1 c_1,2 c_1,3 … c_1,C
c_2,1 c_2,2 c_2,3 … c_2,C
…
c_R,1 c_R,2 c_R,3 … c_R,C
（ただし 1 ≦ R, C ≦ 50, 1 ≦ sy, gy ≦ R かつ 1 ≦ sx, gx ≦ C
c_i,1 c_i,2 c_i,3 … c_i,C の各文字の間には半角スペースなし
各文字は . もしくは # のいずれか）入力例
7 8
2 2
4 5
########
#……#
#.######
#..#…#
#..##..#
##…..#
########出力例
11
最小移動手数を2次元配列 cost に記憶していきます。副産物としてそれ以外のマスに対する最短手数もわかります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int R, C; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); R = vs[0]; C = vs[1]; } int sy, sx; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); sy = vs[0] - 1; sx = vs[1] - 1; } int gy, gx; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); gy = vs[0] - 1; gx = vs[1] - 1; } char[,] map = new char[R, C]; for (int row = 0; row < R; row++) { char[] vs = Console.ReadLine().ToArray(); for (int col = 0; col < C; col++) map[row, col] = vs[col]; } // その地点にたどりつくために要する手数 // この最小値を求めたいので大きな値で初期化しておく int[,] cost = new int[R, C]; for (int row = 0; row < R; row++) { for (int col = 0; col < C; col++) cost[row, col] = int.MaxValue; } Queue<int> qx = new Queue<int>(); Queue<int> qy = new Queue<int>(); qx.Enqueue(sx); qy.Enqueue(sy); // スタート地点にたどりつくために要する手数は 0 手 cost[sy, sx] = 0; int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; while (qx.Count > 0) { int x = qx.Dequeue(); int y = qy.Dequeue(); for (int i = 0; i < 4; i++) { // 次に移動するマスを取得する // 次に移動するマスにたどり着くために必要な手は cost[y, x] + 1 手 int nx = x + dx[i]; int ny = y + dy[i]; int nc = cost[y, x] + 1; // 次に移動するマスが配列外であったり移動不可の地点（#）であればなにもしない // そこにたどり着くための最小手数の暫定値を超える場合もなにもしない if (nx < 0 || ny < 0 || nx >= C || ny >= R) continue; if (map[ny, nx] == '#' || cost[ny, nx] <= nc) continue; // 次に移動するマスの座標を Queue に格納する // 次に移動するマスにたどり着くための暫定最小手数を配列にセットする cost[ny, nx] = nc; qx.Enqueue(nx); qy.Enqueue(ny); } } Console.WriteLine(cost[gy, gx]); } } |
D – Grid Repainting
縦 H マス, 横 W マスに広がるマス目があり、各マスは白または黒で塗られている。上から i 番目で左から j 番目のマスを (i, j) で表す。このマス目を使って次のようなゲームをしたい。
ゲームの開始時点ではマス (1, 1) にゲームキャラクター「けぬす君」がいる. プレイヤーはけぬす君を上下左右の 4 方向のいずれかに 1 マスだけ動かすことを繰り返す。けぬす君が白いマスだけを通って (H, W) にたどり着けばゲームクリアとなる。ゲームを開始する前にすぬけ君はいくつかの白いマス目の色を黒に変えることができる。ただしマス (1, 1) と (H, W) の色を変えることはできない。
ゲームをクリアしたときゲームの開始前にマスの色を変えた回数がスコアとなる。そのとき可能性のある最大のスコアを求めなさい。ただしどのようにマス目の色を変えてもけぬす君が (H, W) にたどり着くことができない場合は -1 と出力しなさい。
入力
H W
‘#’，’.’ からなる W 文字の文字列が H 行
（ただし 2 ≦ H, W ≦ 50。
‘#’は最初から黒で塗られている部分，’.’は白で塗られている部分である)
これはこのように考えてよいのではないでしょうか？
クリアしたときゲームの開始前にマスの色を黒に変えた回数がスコアとなり、スコアを最大にするのであれば必要最小限の部分だけ残してすべて黒く塗ってしまえばよい。白いまま残すべきマスの個数は最短手順に1を足した数である。
ということで（マスの総数）-（最初から黒だったマスの数）-（塗らずに残すべきマスの数）が答えということになります。ただしゴールにたどり着けない場合があるのでそれも考えなければなりません。これは幅優先探索の処理が終わったときにゴールまでの最短手数を記録する部分が初期値から変わっているかでわかります。初期値のままだと “-1” を出力することになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int H, W; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); H = vs[0]; W = vs[1]; } bool[,] map = new bool[H, W]; // 通ることができるか？ int blackCount = 0; for (int row = 0; row < H; row++) { char[] vs = Console.ReadLine().ToArray(); for (int col = 0; col < W; col++) { if (vs[col] == '#') blackCount++; else map[row, col] = true; } } int sx = 0; // スタート地点 int sy = 0; int gx = W - 1; // ゴール int gy = H - 1; int[,] costs = new int[H, W]; for (int row = 0; row < H; row++) { for (int col = 0; col < W; col++) costs[row, col] = int.MaxValue; } costs[sy, sx] = 0; Queue<int> qx = new Queue<int>(); Queue<int> qy = new Queue<int>(); qx.Enqueue(sx); qy.Enqueue(sy); int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; while (qx.Count > 0) { int x = qx.Dequeue(); int y = qy.Dequeue(); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; int ncost = costs[y, x] + 1; if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue; if (!map[ny, nx]) continue; if (costs[ny, nx] <= ncost) continue; costs[ny, nx] = ncost; qx.Enqueue(nx); qy.Enqueue(ny); } } // costs[gy, gx] が初期値より少なくなっていればゴールにたどり着ける if (costs[gy, gx] < int.MaxValue) { int whiteCount = costs[gy, gx] + 1; // 塗らずに残すべきマスの数 // （マスの総数）-（最初から黒だったマスの数）-（塗らずに残すべきマスの数）が答え Console.WriteLine(H * W - blackCount - whiteCount); } else Console.WriteLine(-1); } } |
最短手数を複数回求める
今年も JOI 町のチーズ工場がチーズの生産を始め，ねずみが巣から顔を出した。JOI 町は東西南北に区画整理されていて各区画は巣、チーズ工場、障害物、空き地のいずれかである。ねずみは巣から出発して全てのチーズ工場を訪れチーズを 1 個ずつ食べる。
この町には N 個のチーズ工場があり、どの工場も 1 種類のチーズだけを生産している．チーズの硬さは工場によって異なっており、硬さ 1 から N までのチーズを生産するチーズ工場がちょうど 1 つずつある。
ねずみの最初の体力は 1 であり、チーズを 1 個食べるごとに体力が 1 増える。ただしねずみは自分の体力よりも硬いチーズを食べることはできない。
ねずみは東西南北に隣り合う区画に 1 分で移動することができるが障害物の区画には入ることができない。チーズ工場をチーズを食べずに通り過ぎることもできる。すべてのチーズを食べ終えるまでにかかる最短時間を求めるプログラムを書け。ただしねずみがチーズを食べるのにかかる時間は無視できる。
入力
H W N
‘S’，’1’，’2’，…，’9’，’X’，’.’ からなる W 文字の文字列が H 行
（ただし 1 ≦ H, W ≦1000, 1 ≦ N ≦ 9)巣 S
障害物 X
空き地 .
硬さ i のチーズを生産する工場は数字
ねずみはすべてのチーズを食べられることが保証されている
これは硬さ 1 から N まで順番に回ればよいのではないでしょうか？ 巣から硬さ1のチーズ工場へ、さらにそこから硬さ1のチーズ工場へという具合に。ねずみはすべてのチーズを食べられることが保証されているため、障害物で食べることはできないということはないようです。
上記のコードはスタート地点からゴールに到達すれば終わりでしたが、今回はゴール地点が新しいスタート地点となって新しいゴールを目指すという処理を繰り返します。最短手数を記録する配列もそのつど作り直します。
マップの縦横が最大で1000であること、最短経路を探す繰り返しの回数が最大で9回なので、以下のコードで充分間に合います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int H, W, N; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); H = vs[0]; W = vs[1]; N = vs[2]; } bool[,] map = new bool[H, W]; // 通ることができるか？ int sx = 0; // 巣がある座標 int sy = 0; int[] gxs = new int[N]; // 工場（当面のゴール）がある座標。 int[] gys = new int[N]; char[] numbers = { '1', '2', '3', '4', '5', '6', '7', '8', '9', }; for (int row = 0; row < H; row++) { char[] vs = Console.ReadLine().ToArray(); for (int col = 0; col < W; col++) { map[row, col] = vs[col] == 'X' ? false : true; if (vs[col] == 'S') { sx = col; sy = row; } // vs[col] が数字であれば int型に変換する。 // ゴールのひとつの座標として記録しておく if (numbers.Any(_ => _ == vs[col])) { int num = int.Parse(vs[col].ToString()); gxs[num - 1] = col; gys[num - 1] = row; } } } int ans = 0; for (int i = 0; i < N; i++) { int gx = gxs[i]; // 工場がある座標 int gy = gys[i]; // あとは幅優先探索で最短経路を探す int[,] costs = new int[H, W]; for (int row = 0; row < H; row++) { for (int col = 0; col < W; col++) costs[row, col] = int.MaxValue; } costs[sy, sx] = 0; Queue<int> qx = new Queue<int>(); Queue<int> qy = new Queue<int>(); qx.Enqueue(sx); qy.Enqueue(sy); int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; while (qx.Count > 0) { int x = qx.Dequeue(); int y = qy.Dequeue(); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; int ncost = costs[y, x] + 1; if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue; if (!map[ny, nx]) continue; if (costs[ny, nx] <= ncost) continue; costs[ny, nx] = ncost; qx.Enqueue(nx); qy.Enqueue(ny); } } ans += costs[gy, gx]; sx = gx; // ここが新しい出発点となる sy = gy; } Console.WriteLine(ans); } } |
迷路内の移動にかかるコスト
これまで迷路内を移動するときに最短手数を記録する手法を使いましたが、移動するときには移動先によってコストが必要となり、コストの最小値を問うような問題も出題されます。器物損壊！高橋君はそんな問題です。
彼の住む街は長方形の形をしており、格子状の区画に区切られています。区画は道または塀のどちらかであり、高橋君は道を東西南北に移動できますが斜めには移動できません。また、塀の区画は通ることができません。高橋君の家から魚屋までの道のりは非常に複雑なため、単純に歩くだけでは辿り着くことは困難です。
しかし、高橋君は腕力には自信があるので道に上下左右で面している塀を 2 回までなら壊して道にすることができます。高橋君が魚屋に辿り着くことができるかどうか答えてください。
入力
H W
‘s’，’g’, ‘#’，’.’ からなる W 文字の文字列が H 行（ただし 1 ≦ H, W ≦ 500）
‘s’ : その区画が家であることを表す。
‘g’ : その区画が魚屋であることを表す。
‘.’ : その区画が道であることを表す。
‘#’ : その区画が塀であることを表す。
移動するためのコストを考えます。塀以外の場所に移動するのであればコストは0、塀がある場所に移動するのであればコスト1が必要であるということにして、魚屋にたどりつくまでの最小コストを考えます。魚屋にたどり着くためのコストが破壊しなければならない壁の数です。これが2以下であれば”YES”を出力し、それよりも大きければ”NO”を出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int H, W; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); H = vs[0]; W = vs[1]; } bool[,] isWalls = new bool[H, W]; // 通ることができるか？ int sx = 0; // スタート地点 int sy = 0; int gx = 0; // ゴール int gy = 0; for (int row = 0; row < H; row++) { char[] vs = Console.ReadLine().ToArray(); for (int col = 0; col < W; col++) { if (vs[col] == '#') isWalls[row, col] = true; if (vs[col] == 's') { sx = col; // スタート地点を取得 sy = row; } if (vs[col] == 'g') { gx = col; // ゴール地点を取得 gy = row; } } } int[,] costs = new int[H, W]; for (int row = 0; row < H; row++) { for (int col = 0; col < W; col++) costs[row, col] = int.MaxValue; } costs[sy, sx] = 0; Queue<int> qx = new Queue<int>(); Queue<int> qy = new Queue<int>(); qx.Enqueue(sx); qy.Enqueue(sy); int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; while (qx.Count > 0) { int x = qx.Dequeue(); int y = qy.Dequeue(); for (int k = 0; k < 4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue; int ncost = isWalls[ny, nx] ? costs[y, x] + 1 : costs[y, x]; if (costs[ny, nx] <= ncost) continue; costs[ny, nx] = ncost; qx.Enqueue(nx); qy.Enqueue(ny); } } if(costs[gy, gx] <= 2) Console.WriteLine("YES"); else Console.WriteLine("NO"); } } |
開始点が複数ある幅優先探索
縦 H 行、横 W 列の白黒に塗られたマス目が与えられます。 マス目の色は白か黒です。
すべてのマスが黒色になるまで、以下の操作を繰り返し行います。辺を共有して隣接するマスの中に、黒色のマスが一つ以上存在するような白色のマスすべてが黒色になる。
何回の操作を行うことになるか求めてください。 ただし、最初に与えられるマス目には少なくとも 1 つ黒色のマスが存在します。
入力
H W
‘#’，’.’ からなる W 文字の文字列が H 行（ただし 1 ≦ H, W ≦ 1000）
‘.’ : そのマスの色は白であることを表す。
‘#’ : そのマスの色は黒であることを表す。
これも幅優先探索なのですが、開始点が複数あります。そこでまずは複数ある開始点の座標を取得し、それをQueueに格納します。あとはほとんど同じですが、すべてのマスを探索するに要した回数を答えなければなりません。ここでは次に探索する座標だけでなく、これまでの探索回数もQueueに格納することにしました。これで回数を数えることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int H, W; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); H = vs[0]; W = vs[1]; } bool[,] isBlacks = new bool[H, W]; // マスは黒かどうか？ List<int> sXs = new List<int>(); // 開始点の座標。複数あるかもしれない。 List<int> sYs = new List<int>(); // 個数は取得するまでわからないのでリストに格納する for (int row = 0; row < H; row++) { char[] vs = Console.ReadLine().ToArray(); for (int col = 0; col < W; col++) { if (vs[col] == '#') { isBlacks[row, col] = true; sXs.Add(col); sYs.Add(row); } } } Queue<int> qX = new Queue<int>(); Queue<int> qY = new Queue<int>(); Queue<int> qCount = new Queue<int>(); for (int i = 0; i < sXs.Count; i++) { qX.Enqueue(sXs[i]); qY.Enqueue(sYs[i]); qCount.Enqueue(0); } int[] dx = { 1, -1, 0, 0 }; int[] dy = { 0, 0, 1, -1 }; int ans = 0; while (qX.Count > 0) { int x = qX.Dequeue(); int y = qY.Dequeue(); int count = qCount.Dequeue(); for (int k = 0; k < 4; k++) { // 次に訪問するマスの座標 int nx = x + dx[k]; int ny = y + dy[k]; // 配列の範囲外の場合はなにもしない // すでに黒く塗られているマスも次回の訪問対象ではない if (nx < 0 || ny < 0 || nx >= W || ny >= H) continue; if (isBlacks[ny, nx]) continue; isBlacks[ny, nx] = true; qX.Enqueue(nx); qY.Enqueue(ny); qCount.Enqueue(count + 1); // 回数をインクリメントする } ans = Math.Max(ans, count); // 回数の最大値を記憶する } Console.WriteLine(ans); } } |
