[AOJ] No. 0632 休憩スペース (Refreshment Area)
問題
方針
縦方向と横方向に分けて考える
休憩スペースは南北方向または東西方向に置くことが可能なので、縦方向と横方向に分けて考えます。
連続する空マスを数える
ある方向に向かって連続する空マスを数え、その値が \( D \) よりも大きい時、そのマスを末端として休憩スペースを置くことができます。つまり、休憩スペースの末端を調べることで休憩スペースを設けるパターンの場合の数が分かります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, M, D; cin >> N >> M >> D; char c[N][M]; for (int i = 0; i < N; i++) { string s; cin >> s; for (int j = 0; j < M; j++) { c[i][j] = s[j]; } } int ans = 0; for (int i = 0; i < N; i++) { int cnt = 0; for (int j = 0; j < M; j++) { if (c[i][j] == '.') cnt++; else cnt = 0; if (cnt >= D) ans++; } } for (int i = 0; i < M; i++) { int cnt = 0; for (int j = 0; j < N; j++) { if (c[j][i] == '.') cnt++; else cnt = 0; if (cnt >= D) ans++; } } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません