第18回ABC C問題「菱型カウント」

C: 菱型カウント - AtCoder Beginner Contest #018 | AtCoder

解法：３０点解法を枝刈りする
O(RCN)(Nはxの数)ぐらいになるので、Nが300以下ぐらいのケースに対して枝刈りを適用すると時間内に解くことができる。
枝刈りは
・確実に範囲外になってしまう座標(計算が結構めんどくさい)
・近くにxが無い座標
どちらかの条件を満たす場合に行う。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <math.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <sstream>
#include <string>

using namespace std;

#define FOR(I,N) for(int I = 0; I < (int)(N); I++)
#define FIN(V) cout<<V<<endl
#define pb push_back
#define INF (1 << 30)

typedef pair<int, int> P;

string sValueOf(int v){stringstream ss;ss<<v;return ss.str();}
int parseInt(string v){int i;stringstream ss(v);ss>>i;return i;}
void fast_io() {cin.tie(0); ios::sync_with_stdio(false);}

int map[504][504];
int h,w,k;

vector<P> black;

int main(){
	int i,j,m,l;
	cin>>h>>w>>k;
	fill_n(*map,504*504,1);
	string in;
	FOR(i,h){
		cin>>in;
		FOR(j,w){
			char c = in[j];
			if(c=='o'){
				map[j+1][i+1] = 0;
			}else{
				map[j+1][i+1] = 1;
				black.pb(P(j+1,i+1));
			}
		}
	}
	int ans = 0;
	int dis = 2*k-1;
	int size = black.size();
	FOR(i,h)FOR(j,w){
		int x = j+1;
		int y = i+1;
		if(j<k-1)continue;
		if(w-j<=k-1)continue;
		if(h-i<=dis-1)continue;

		if(size<=300){
			int cy = y+k-1;
			double mini = INF;
			FOR(m,size){
				mini = min(mini,sqrt(pow(black[m].first-x,2.0)+pow(black[m].second-cy,2.0)));
			}
			if(mini>k){ans++;continue;}
		}

		int width = 1;
		bool able = true;
		FOR(m,dis){
			if(map[x][y+m]){able = false;break;}
		}
		if(!able)continue;
		FOR(m,dis){
			FOR(l,width){
				if(map[x+l][y]){able = false;break;}
			}
			if(!able)break;
			y++;
			if(m>=k-1){///後半
				x++;
				width-=2;
			}else{
				x--;
				width+=2;
			}
		}
		if(able){
			ans++;
		}
	}

	cout<<ans<<endl;
	return 0;
}