[AOJ] No. 0610 気象予報士 (Weather Forecaster)

2019年7月3日

問題

方針

西側にある一番近い雲までの距離

小区間 \( (i , j) \) からその区間を含めて西側にある一番近い雲までの距離が答えになります。もし、雲が存在しなければ \( -1 \) となります。どのようにして求めるかですが、二次元配列 \( t \) において、小区間 \( (i , j) \) の一番近い雲までの距離を \( t_{i, j} \) とします。まず初めに、\( t \) を \( -1 \) で初期化します。その後、\( (i, j) \) が 'c’ となっている区間に対して、\( t_{i, j} = 0\) とします。あとは東側に向かってカウントしていくだけです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  int H, W;
  cin >> H >> W;
  char c[H][W];
  for (int i = 0; i < H; i++) {
    string s;
    cin >> s;
    for (int j = 0; j < W; j++) {
      c[i][j] = s[j];
    }
  }
  int t[H][W];
  memset(t, -1, sizeof(t));
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (c[i][j] == 'c') t[i][j] = 0;
    }
  }
  for (int i = 0; i < H; i++) {
    for (int j = 1; j < W; j++) {
      if (t[i][j - 1] != -1) {
        if (t[i][j] == -1) t[i][j] = t[i][j - 1] + 1;
        else t[i][j] = min(t[i][j], t[i][j - 1] + 1);
      }
    }
  }
  for (int i = 0; i < H; i++) {
    for (int j = 0; j < W; j++) {
      if (j == 0) cout << t[i][j];
      else cout << " " << t[i][j];
    }
    cout << "\n";
  }
  return 0;
}