CF1579C Ticks

题意

\(n \times m\) 的棋盘，左上角和右下角坐标分别为 \((1, 1), (n, m)\)，一开始每个格子为白色。

每次操作可以选择一个格子 \((x, y)\) 以及左上角和右上角方向的 \(d\) 个连续格子染成黑色，并将其称为一个大小为 \(d\) 的对勾图案。如果多个对勾图案重复对一个格子染色，该格子颜色保持黑色不变。

现在给你一个棋盘，请问棋盘上的黑色格子是否可以由若干个大小至少为 \(k\) 的对勾图案染色而成。

思路

一道明显的深搜

从下往上枚举（即，从根开始枚举）

最开始，先搜索一下判断能否画出一个大于\(k\)的对勾，如果可以，那么就开始画

最后，判断一下是否每一个需要被染色的格子都被染色了

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
char c[20][20];
int n,m,k,minn;
bool vis[20][20];
void dfs(int x,int y,int now)
{
	// cout<<x<<" "<<y<<":\n";
	int dx=x-now-1,dy1=y-now-1,dy2=y+now+1;
	if(dx<1 || dy1<1 || dy2<1 || dx>n || dy1>m || dy2>m || c[dx][dy1]!='*' || c[dx][dy2]!='*') minn=min(now,minn);
	else
	{
		// cout<<dx<<": dy={"<<dy1<<" ,"<<dy2<<"}\n";
		now++;
		vis[dx][dy1]=1,vis[dx][dy2]=1;
		dfs(x,y,now);
	}
}
bool check(int x,int y,int now)
{
	int dx=x-now-1,dy1=y-now-1,dy2=y+now+1;
	if(dx<1 || dy1<1 || dy2<1 || dx>n || dy1>m || dy2>m || c[dx][dy1]!='*' || c[dx][dy2]!='*') return now>=k;
	else
	{
		now++;
		return check(x,y,now);
	}
}
void run()
{
	cin>>n>>m>>k;minn=1e9+10;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>c[i][j];
			vis[i][j]=0;
		}
	for(int i=n;i>=1;i--)
	{
		for(int j=m;j>=1;j--)
		{
			if(c[i][j]=='*' && check(i,j,0))
			{
				dfs(i,j,0);
				vis[i][j]=1;
			}
		}
	}
	bool ans=1;
	for(int i=1;i<=n && ans;i++)
		for(int j=1;j<=m && ans;j++)
		{
			if(vis[i][j]==0 && c[i][j]=='*') ans=0;
		}
	cout<<(ans?"Yes":"No")<<endl;
}
signed main()
{
	int t;
	cin>>t;
	while(t--) run();
	system("pause");
	return 0;
}