AcWing 4263. 走路回家
原题链接
简单
作者:
SpiderQ
,
2022-08-16 21:31:36
,
所有人可见
,
阅读 187
(DFS+剪枝)
可行性剪枝:
1.当前改变方向次数 大于 k return;
2.当前改变方向次数 等于 k , 但当前位置不在 最后一行 或 最后一列 return;
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=55;
int n,k,ans;
char g[N][N];
bool st[N][N];
int dx[2]={0,1},dy[2]={1,0};
void dfs(int x,int y,int cnt,int last)
{
if(cnt==k && x!=n-1 && y!=n-1)return;
if(cnt>k)return;
if(x==n-1 && y==n-1)
{
++ans;
return;
}
for(int i=0;i<2;++i)
{
int a=x+dx[i],b=y+dy[i];
if(a<0 || a>=n || b<0 || b>=n)continue;
if(st[a][b] || g[a][b]=='H')continue;
st[a][b]=1;
dfs(a,b,cnt+(last!=-1 && i!=last),i);
st[a][b]=0;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=0;i<n;++i)scanf("%s",g[i]);
ans=0;
memset(st,0,sizeof(st));
dfs(0,0,0,-1);
printf("%d\n",ans);
}
return 0;
}