Submission #332037

---

Source Code Expand

#include<iostream>
#include<string>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000
int r,c,k;
string zu[501];
int t1[501][501];
int t2[501][501];
int t3[501][501];
int t4[501][501];
int dp[501][501];
int ans;
int main()
{
	cin>>r>>c>>k;
	rep(i,r)cin>>zu[i];
	rep(i,501)rep(j,501)
	{
		t1[i][j]=INF;
		t2[i][j]=INF;
		t3[i][j]=INF;
		t4[i][j]=INF;
	}
	rep(i,r)rep(j,c)
	{
		if(zu[i][j]=='x')
		{
			t1[i][j]=0;
			continue;
		}
		if(i==0&&j!=0)
		{
			t1[i][j]=t1[i][j-1]+1;
		}
		if(i!=0&&j==0)
		{
			t1[i][j]=t1[i-1][j]+1;
		}
		if(i!=0&&j!=0)
		{
			t1[i][j]=min(t1[i-1][j]+1,t1[i][j-1]+1);
		}
	}
	rep(i,r)rep(j,c)
	{
		if(zu[r-1-i][j]=='x')
		{
			t2[r-1-i][j]=0;
			continue;
		}
		if(i==0&&j!=0)
		{
			t2[r-1-i][j]=t2[r-1-i][j-1]+1;
		}
		if(i!=0&&j==0)
		{
			t2[r-1-i][j]=t2[r-i][j]+1;
		}
		if(i!=0&&j!=0)
		{
			t2[r-1-i][j]=min(t2[r-i][j]+1,t2[r-1-i][j-1]+1);
		}
	}
	rep(i,r)rep(j,c)
	{
		if(zu[i][c-1-j]=='x')
		{
			t3[i][c-1-j]=0;
			continue;
		}
		if(i==0&&j!=0)
		{
			t3[i][c-1-j]=t3[i][c-j]+1;
		}
		if(i!=0&&j==0)
		{
			t3[i][c-1-j]=t3[i-1][c-1-j]+1;
		}
		if(i!=0&&j!=0)
		{
			t3[i][c-1-j]=min(t3[i][c-j]+1,t3[i-1][c-1-j]+1);
		}
	}
	rep(i,r)rep(j,c)
	{
		if(zu[r-1-i][c-1-j]=='x')
		{
			t4[r-1-i][c-1-j]=0;
			continue;
		}
		if(i==0&&j!=0)
		{
			t4[r-1-i][c-1-j]=t4[r-1-i][c-j]+1;
		}
		if(i!=0&&j==0)
		{
			t4[r-1-i][c-1-j]=t4[r-i][c-1-j]+1;
		}
		if(i!=0&&j!=0)
		{
			t4[r-1-i][c-1-j]=min(t4[r-1-i][c-j]+1,t4[r-i][c-1-j]+1);
		}
	}
	int ss;
	k--;
	rep(i,r)
	{
		rep(j,c)
		{
			ss=INF;
			ss=min(ss,t1[i][j]);
			ss=min(ss,t2[i][j]);
			ss=min(ss,t3[i][j]);
			ss=min(ss,t4[i][j]);
			dp[i][j]=ss;
			if(i-k>=0&&j-k>=0&&i+k<r&&j+k<c&&dp[i][j]>k)ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result