Official

D - Bombs Editorial by yuto1115

解説

以下のアルゴリズムを for 文によって実装すればよいです。

  1. \(R\times C\) の bool 配列 \(v\) を用意し、最初全ての要素を False で初期化する。
  2. 爆弾がある全てのマス \((i,j)\) について以下を行う。
    • \((i,j)\) にある爆弾の爆発が効果を及ぼすような全てのマス \((k,l)\) について、\(v[k][l]\) を True にする。
  3. \(v[i][j]\) が True であるような全てのマス \((i,j)\) について、\(B[i][j]\). にする。

上記の 2. において直接 \(B[k][l]\). にしてしまうと、\((k,l)\) に爆弾があった場合、その爆弾の爆発を考慮し損ねてしまう可能性があることに注意してください。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

int main() {
    int r, c;
    cin >> r >> c;
    vector <string> b(r);
    for (string &s: b) cin >> s;
    
    vector blasted(r, vector<bool>(c));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (!isdigit(b[i][j])) continue;
            int power = b[i][j] - '0';
            for (int ni = 0; ni < r; ni++) {
                for (int nj = 0; nj < c; nj++) {
                    if (abs(i - ni) + abs(j - nj) <= power) blasted[ni][nj] = true;
                }
            }
        }
    }
    
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (blasted[i][j]) b[i][j] = '.';
        }
    }
    
    for (string &s: b) cout << s << '\n';
}

posted:
last update: