C - 器物損壊！高橋君

コメント歓迎です。

今回も幅優先探索の応用問題です。

0-1-BFSと呼ばれている手法のようです。

タイトルの勢いが結構好きです。

問題

AtCoder 版！蟻本 (初級編) - Qiitaより

arc005.contest.atcoder.jp

方針

今回の問題で初めてdequeというものを使いました。

dequeは普通のqueueとは違い、先頭にも最後尾にもpushできます。

今回の使い方としては優先度の高いものは先頭にpushし、
優先度が低いものは最後尾にpushします。

そうすることによって優先度が高いものからpopされ、処理が進むことになります。

迷路は通路('.', 's', 'g')か壁('#')の二種類しかなく、通路を優先して処理しています。

変数scoreの値は壁を一度壊さないと進めないマスは"1"、二度なら"2"、三度なら"3"といった具合になります。

下に例を示します。

迷路

s	.	.	.	.	.	.	.	.	.
#	#	#	#	#	#	#	#	#	.
#	.	.	.	.	.	.	.	#	.
#	.	.	#	#	#	#	.	#	.
#	#	.	.	.	.	#	.	#	.
#	#	#	#	#	.	#	.	#	.
g	#	#	.	#	.	#	.	#	.
#	#	#	.	#	.	#	.	#	.
#	#	#	.	#	.	#	.	#	.
#	.	.	.	.	.	#	.	.	.

処理後のscore

0	0	0	0	0	0	0	0	0	0
1	1	1	1	1	1	1	1	1	0
1	0	0	0	0	0	0	0	1	0
1	0	0	1	1	1	1	0	1	0
2	1	0	0	0	0	1	0	1	0
3	2	1	1	1	0	1	0	1	0
2	2	1	0	1	0	1	0	1	0
3	2	1	0	1	0	1	0	1	0
2	1	1	0	1	0	1	0	1	0
1	0	0	0	0	0	1	0	0	0

ゴールマスのscoreが2以下であれば壁を壊す回数が2回以下でたどり着けることになります。

コード(AC)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
// 宣言
char maze[500][500]; // 迷路データ
int H; // 高さ
int W; // 幅
  
int sh, sw; // スタート地点
int gh, gw; // ゴール地点
vector< vector<int> > score(500, vector<int> (500, 100)); // 手数
bool visited[500][500]; // 訪問履歴
const int dh[] = {1, -1, 0, 0};
const int dw[] = {0, 0, 1, -1};
  
// 幅優先探索
void bfs(int i, int j) {
  // キューを準備
  deque<pair<int,int> > Q;
  // スタート地点のスコアを0にセット
  score[i][j] = 0;
  // スタート地点の座標をキューにプッシュ
  Q.push_back(make_pair(i, j));
  // キューが空になるまで処理を実行
  while(!Q.empty()) {
    // 探索の起点となる座標を記憶してからポップ
    pair<int,int> q = Q.front();
    Q.pop_front();
    int h = q.first;
    int w = q.second;
    // 起点を元に座標を移動
    for (int k = 0; k < 4; k++) {
      int nh = h + dh[k];
      int nw = w + dw[k];
      // 移動先が迷路の範囲外なら処理をスキップ
      if (nh < 0 || nh >= H || nw < 0 || nw >= W) {
        continue;
      }
      // 移動先が壁ならdequeの最後尾にプッシュ
      if (score[nh][nw] > (score[h][w] + 1) && maze[nh][nw] == '#') {
        Q.push_back(make_pair(nh, nw));
        // 移動先のスコアを起点のスコア+1にする
        score[nh][nw] = score[h][w] + 1;
      }
      // そうでなければdequeの先頭にプッシュ
      if (score [nh][nw] > score[h][w] && maze[nh][nw] != '#'){
        Q.push_front(make_pair(nh, nw));
        // 移動先のスコアを起点のスコアと同じにする
        score[nh][nw] = score[h][w];
      }
    }
  }
}
  
int main() {
  // 入力
  cin >> H >> W;
  // 迷路データ
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      cin >> maze[i][j];
      // スタート地点を記録
      if (maze[i][j] == 's') {
        sh = i;
        sw = j;
      }
      // ゴール地点を記録
      if (maze[i][j] == 'g') {
        gh = i;
        gw = j;
      }
    }
  }
  
  // 幅優先探索
  bfs(sh, sw);
  
  // 出力
  cout << (score[gh][gw] <= 2 ? "YES" : "NO") << endl;
  return 0;
}