幅優先探索（3題）
幅優先探索が使える問題
「プログラミングコンテストチャレンジブック」第２版（マイナビ）の章末(p.125)で紹介されている練習問題を淡々と解いている。
こういう基本的なアルゴリズムは問題を見たら手が勝手に動くくらいに練習しないと。
幅優先探索が使える問題の特徴は、
・迷路のゴールまでの最短距離はだいたい幅優先探索
・全探索したいけど深さがよくわからない
って感じ。
ちょっとずつ深くしながら幅優先で探索していけば、ゴールまでの最短距離を探しやすいよね、っていうふうに直感的に理解している。
AOJ0558: Cheeze
問題 Cheese | Aizu Online Judge
ネズミにチーズ工場を順番に回らせる最短距離を求める。
迷路の最短距離を求める幅優先探索を繰り返す。
#include <iostream> #include <queue> using namespace std; const int MAX = 1000; const int INF = 10000000; typedef pair<int, int> P; int h,w,n; // 移動の4方向 int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; // チーズ工場のマップ short field[MAX][MAX]; // スタートから各点への最短距離 int d[MAX][MAX]; // 幅優先探索の関数の返り値用 typedef struct { int x; int y; int cnt; } Cheeze; // 地点(sx,sy)から目標地点（工場i）までの最短距離を求める幅優先探索 Cheeze bfs(int sx, int sy, char i) { // スタート地点は距離0 d[sy][sx] = 0; queue<P> qu; qu.push(P(sx, sy)); // 工場iに達するまで繰り返す while (true) { P p = qu.front(); qu.pop(); // ゴールなら終了 if (field[p.second][p.first] == i) { Cheeze res = {p.first, p.second, d[p.second][p.first]}; return res; } // 4方向 for (int j = 0; j < 4; j++) { int nx = p.first + dx[j]; int ny = p.second + dy[j]; // 移動可能判定など if (nx >= 0 && nx < w && ny >= 0 && ny < h && d[ny][nx] == INF && field[ny][nx] != -1) { qu.push(P(nx,ny)); d[ny][nx] = d[p.second][p.first] + 1; } } } } int main() { // 入力 int sx, sy; int cnt = 0; Cheeze cheeze; cin >> h >> w >> n; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { char cel; cin >> cel; if (cel == 'X') { field[i][j] = -1; } else if (cel == '.') { field[i][j] = 0; } else if (cel == 'S') { field[i][j] = 0; sx = j; sy = i; } else { field[i][j] = (short)(cel - '0'); } } } // 計算 for (int i = 1; i <= n; i++) { // 最短距離dの初期化 for (int j = 0; j < MAX; j++) { for (int k = 0; k < MAX; k++) { d[j][k] = INF; } } cheeze = bfs(sx, sy, i); // スタート地点を更新 sx = cheeze.x; sy = cheeze.y; cnt += cheeze.cnt; } // 出力 cout << cnt << endl; }
POJ3669: Meteor Shower
問題 3669 -- Meteor Shower
隕石が次々に降ってくるから少女を安全地帯に避難させろ。
各座標に隕石が降ってくる時刻を記録しておいて、あとは幅優先で適当に少女に歩かせる。
#include <iostream> #include <algorithm> #include <queue> using namespace std; const int MAX = 302; const int INF = 10000000; typedef pair<int, int> P; int h,w,n; // 移動の4方向 int dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; // 各座標に隕石が落ちる時間を格納する int field[MAX][MAX]; // 各座標に到着したときの時刻 int d[MAX][MAX]; // 幅優先探索 // 移動した先がすでに隕石が落ちていたら死亡させていく int bfs() { // スタート地点は(0,0) queue<P> qu; qu.push(P(0, 0)); d[0][0] = 0; // スタート地点に最初から隕石が落ちていたら終了 if (field[0][0] == 0) return -1; // queueが空になるまでループ while (qu.size()) { // queueから1つ座標を取り出す P p = qu.front(); int x = p.first; int y = p.second; qu.pop(); // INFなら終了 if (field[x][y] == INF) { return d[x][y]; } // 4方向 for (int j = 0; j < 4; j++) { int nx = x + dx[j]; int ny = y + dy[j]; // 移動可能判定など if (nx >= 0 && nx <= MAX && ny >= 0 && ny <= MAX && d[x][y] + 1 < field[nx][ny] && d[nx][ny] == INF) { d[nx][ny] = d[x][y] + 1; qu.push(P(nx,ny)); } } } // quが空になったら安全地帯に到達できない return -1; } int main() { // 入力 for (int i = 0; i < MAX; i++) { for (int j = 0; j < MAX; j++) { field[i][j] = INF; d[i][j] = INF; } } int m; cin >> m; int x, y, t; for (int i = 0; i < m; i++) { cin >> x >> y >> t; field[x][y] = min(t,field[x][y]); // 周囲にも隕石の影響がある for (int j = 0; j < 4; j++) { int nx = abs(x + dx[j]); int ny = abs(y + dy[j]); field[nx][ny] = min(t, field[nx][ny]); } } // 計算 int res = bfs(); // 出力 cout << res << endl; }
AOJ0121: Seven Puzzle
問題 Seven Puzzle | Aizu Online Judge
数字をスライドさせて整列させるゲーム。スライディングブロックパズルっていうのか。
あらかじめすべての状態の「ゴールまでの最小手数」を求めておく。
// 幅優先探索であらかじめすべての状態の最小手数を計算する // 8!=40320なので、余裕で計算できる // 最終状態01234567からさかのぼって幅優先探索 #include <iostream> #include <queue> #include <map> using namespace std; typedef pair<int, int> P; // 最終状態01234567からある状態にするまでの最小手数 map<string,int> d; void bfs() { // 最終状態への手数は0 string start = "01234567"; d[start] = 0; // キューを作る queue<string> qu; qu.push(start); // キューが空になるまでループ while(qu.size()) { string a = qu.front(); qu.pop(); int i = a.find_first_of('0'); string s[3]; s[0] = a; s[1] = a; s[2] = a; // 上下の交換 int j = (i + 4) % 8; s[0].replace(i,1,1,s[0].at(j)); s[0].replace(j,1,1,'0'); // 右との交換 if (i % 4 != 3) { s[1].replace(i,1,1,s[1].at(i+1)); s[1].replace(i+1,1,1,'0'); } // 左との交換 if (i % 4 != 0) { s[2].replace(i,1,1,s[2].at(i-1)); s[2].replace(i-1,1,1,'0'); } // まだ最終手数がわかっていない文字列をキューにぶっこむ for (int k = 0; k < 3; k++) { if (d.find(s[k]) == d.end()) { qu.push(s[k]); d[s[k]] = d[a] + 1; } } } } int main() { // 先に最小手数のリストを作る bfs(); // 入力と出力 int n; while (true) { string str; for (int i = 0; i < 8; i++) { if (!(cin >> n)) return 0; str += n + '0'; } cout << d[str] << endl; } }
