[C++知识库]Codeforces Round #744 (Div. 3) C. Ticks题解

原题链接

模拟

找到当前为 * 的点，判断它的两上角对角线上的点是否为 *,如果为 * 的数量大于等于d ，标记为真，最后再判断是否所有 * 都为真。

代码

#include<iostream>
#include<cstring>
using namespace std;
char g[20][20];
bool f[20][20];
int n,m,k;

void solve(int x,int y)
{
	int d=0;
	for(int i=x-1,j=y-1,k=y+1;i>=0&&j>=0&&k<m;i--,j--,k++)
	{
		if(g[i][j]=='*'&&g[i][k]=='*')
		{
			d++;
		}else break;
	}
	if(d>=k)
	{
		f[x][y]=true;
		for(int i=x-1,j=y-1,k=y+1;i>=0&&j>=0&&k<m;i--,j--,k++)
		{
			if(g[i][j]=='*'&&g[i][k]=='*')f[i][j]=f[i][k]=true;
			else break;
		}
	}
}

bool flag()
{
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(g[i][j]=='*'&&f[i][j]==false)return false;
		}
	}
	return true;
}

int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		memset(f,false,sizeof f);
		cin>>n>>m>>k;
		for(int i=0;i<n;i++)cin>>g[i];
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<m;j++)
			{
				if(g[i][j]=='*')solve(i,j);
			}
		}
		bool x=flag();
		if(x)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}