分析
dfs相关题目,每次判断坐标能否跳到,若能就继续dfs,最终所有棋子都达到,ans++。
为了让代码更快执行,可以开启优化:
#pragma GCC optimize(2)
#pragma GCC optimize(3)
能使程序的编译效率大大提升。
也可以对cin,cout优化:
ios::sync_with_stdio(false);
这种优化可以来打消iostream的输入、输出缓存,可以节省许多时间,使效率与scanf与printf相差无几。
优化效果展示:
可见优化后将近快了3倍。
C++ 代码
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
int dx[]={-2,-2,-1,-1,1,1,2,2};
int dy[]={1,-1,-2,2,-2,2,-1,1};
int n,m,x_0,y_0,cnt,k,ans,t;
bool st[10][10];
void dfs(int x,int y,int cnt)
{
if(cnt==k) //所有棋子都可以跳到,ans++
{
ans++;
return ;
}
for(int i=0;i<8;i++)
{
int xx=x+dx[i],yy=y+dy[i];
if(xx>=0 && xx<n && yy>=0 && yy<m && !st[xx][yy])
{
st[xx][yy]=true;
dfs(xx,yy,cnt+1);
st[xx][yy]=false;
}
}
}
int main()
{
ios::sync_with_stdio(false); //输入输出优化
cin>>t;
while(t--)
{
cin>>n>>m>>x_0>>y_0;
k=n*m,ans=0;
memset(st,false,sizeof st);
st[x_0][y_0]=true;
dfs(x_0,y_0,1);
cout<<ans<<endl;
}
return 0;
}