第二回 アルゴリズム実技検定 C - ⼭崩し 解説

問題

問題文は本家サイトにあります：第二回 アルゴリズム実技検定 C - ⼭崩し

問題概要

縦 $N$ マス、横 $2N-1$ マスのマス目があります。上から $i$ 行目、左から $j$ 列目のマスは、 $|j-N|\lt i$ を満たしていたら黒、他は白に塗られています。以下は、 $N=3$ のときの例です。

..#..
.###.
#####

'.' が白を、'#' が黒を表しています。ここで、黒いマスのうち、いくつかに 'X' を書いた状態が入力されます。これに対し、以下の操作をした結果を返しなさい。

操作： $i=N-1, N-2,\cdots,1$ の順番で、次の処理を行う。
処理： $2\leqq j \leqq 2N-2$ に対して、マス $(i,j)$ が黒いマスで 'X' が書かれておらず、マス $(i+1,j-1)$, $(i+1,j)$, $(i+1,j+1)$ のうち1つ以上に 'X' が書かれていれば、マス $(i,j)$ に 'X' を書く。

制約

$2\leqq N \leqq 50$

解説

言われた通りの処理を行っていきます。

まずは、状態を配列に格納していきます。1行ずつ格納していきましょう。

次に、下から2行目に対して、黒いマスを見ていきます。マスが '#' の状態で、左下、下、右下のどれかが 'X' かどうかを確認していきます。これを上に向かって続けていけばOKです。C++では、次のように書けます。

#include <iostream>
#include <vector>
using namespace std;

int main() {

  int N; cin >> N;
  vector<string> S(N);
  for (int i = 0; i < N; i++) {
    cin >> S[i];
  }

  for (int i = N - 2; i >= 0; i--) {
    for (int j = 1; j < 2 * N - 2; j++) {
      if (S[i][j] != '#') continue;
      if (S[i + 1][j - 1] == 'X' || S[i + 1][j] == 'X' || S[i + 1][j + 1] == 'X') {
        S[i][j] = 'X';
      }
    }
  }

  for (int i = 0; i < N; i++) {
    cout << S[i] << '\\n';
  }
  return 0;
}