ABC018 C - 菱型カウント

C - 菱型カウント

概要

R行C列のマスがあり、各マスにはoかxのいずれかが記入されている。
整数Kが与えられる。次のような(x, y)の組(R ≦ x ≦ R + K - 1, C ≦ y ≦ C + K - 1)の個数がいくつあるか答えよ。

• |i -x| + |j - y| ≦ K - 1を満たすi, j についてはマス(i, j)の値が全てoである

制約

3 ≦ R, C ≦ 500
2 ≦ K ≦ 500

方針

各x, yについて、 |i -x| + |j - y| ≦ K - 1を満たす各(i, j)マスが全てoであるかを愚直に確認しようとするとO(RCK^2)かかり、間に合わない。

条件確認を効率化する。
各マス(i, j)について、下記の2種類の値を保持する。

• above[i][j]：(i, j)マスとその上方に連続したoがいくつあるか
• below[i][j]：(i, j)マスとその下方に連続したoがいくつあるか

すると各x, yをチェックする際は、xと同じ行にある2K+1個のabove, belowの数値を確認するだけでよくなり、計算量がO(RCK)となり間に合う。

解答

Submission #6943820 - AtCoder Beginner Contest 018

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int R, C, K;
	cin >> R >> C >> K;
 
	vector<string> s(R);
	rep(i, R) cin >> s[i];
 
	vector<vector<int>> above(R, vector<int>(C, 0));
	vector<vector<int>> below(R, vector<int>(C, 0));
 
	for(int c = 0; c < C; c++){
		int cnt = 0;
		for(int r = 0; r < R; r++){
			if(s[r][c] == 'x') cnt = 0;
			else cnt++;
			above[r][c] = cnt;
		}
	}
 
	for(int c = 0; c < C; c++){
		int cnt = 0;
		for(int r = R - 1; r > 0; r--){
			if(s[r][c] == 'x') cnt = 0;
			else cnt++;
			below[r][c] = cnt;
		}
	}
 
	int ans = 0;
	for(int i = K - 1; i <= R - K; i++){
		for(int j = K - 1; j <= C - K; j++){
			bool ok = true;
			for(int c = j - K + 1; c <= j; c++){
				if(above[i][c] < (c - (j - K)) || below[i][c] < (c - (j - K))){
					ok = false;
					break;
				}
			}
 
			for(int c = j + 1; c <= j + K - 1; c++){
				if(above[i][c] < (j + K - c) || below[i][c] < (j + K - c)){
					ok = false;
					break;
				}
			}
 
			if(ok) ans++;
		}
	}
 
	cout << ans << endl;
}