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;
}