Submission #76270003

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
const int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
int main() {
    int H;
    cin >> H;
    int W;
    cin >> W;
    vector<string> field(H);
    for (int i = 0; i < H; i++) {
      cin >> field.at(i);
    }
    // 各セルの最短距離 (訪れていないところは -1 としておく)
    vector<vector<int> > dist(H, vector<int>(W, -1)); 

    // 探索中に各マスはどのマスから来たのかを表す配列 (最短経路長を知るだけなら、これは不要)
    vector<vector<int> > prev_x(H, vector<int>(W, -1));
    vector<vector<int> > prev_y(H, vector<int>(W, -1));

    // 「一度見た頂点」のうち「まだ訪れていない頂点」を表すキュー
    queue<pair<int, int> > que; 
    int sx, sy;
    bool SSR = true;
    bool SSSR = true;
    for (int h = 0; h < H; ++h) {
        for (int w = 0; w < W; ++w) {
            if (field[h][w] == '#') {
                SSR = true;
                SSSR = true;
              for (int i = 0; i < 8; i++) {
                int next_x = h + dx[i];
                int next_y = w + dy[i];
                if (next_x < 0 || next_x > H-1 || next_y < 0 || next_y > W-1) {
                  continue;
                }
                else if (field[next_x][next_y] == '.') {
                  SSR = false;
                }
              }
              if (SSR) {
                SSSR = false;
              }
              if (SSSR) {
                sx = h;
                sy = w;
                que.push(make_pair(sx, sy));
                dist[sx][sy] = 0;
              }
            }
            SSR = true;
            SSSR = true;
        }
    }
    //実行
    while (!que.empty()) {
        pair<int, int> current_pos = que.front(); // キューの先頭を見る (C++ ではこれをしても pop しない)
        int x = current_pos.first;
        int y = current_pos.second;
        que.pop(); // キューから pop を忘れずに

        // 隣接頂点を探索
        for (int direction = 0; direction < 8; ++direction) {
            int next_x = x + dx[direction];
            int next_y = y + dy[direction];
            if (next_x < 0 || next_x >= H || next_y < 0 || next_y >= W) continue; // 場外アウトならダメ

            // まだ見ていない頂点なら push
            if (dist[next_x][next_y] == -1) {
                que.push(make_pair(next_x, next_y));
                dist[next_x][next_y] = dist[x][y] + 1; // (next_x, next_y) の距離も更新
                prev_x[next_x][next_y] = x;  // どの頂点から情報が伝播して来たか、縦方向の座標をメモ
                prev_y[next_x][next_y] = y;  // どの頂点から情報が伝播して来たか、横方向の座標をメモ
            }
        }
    }
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if (dist[i][j]%2 == 0) {
          cout << '#';
        }
        else {
          cout << '.';
        }
      }
      cout << endl;
    }
    return 0;
  }

Submission Info

Judge Result