计蒜客T1217 马走日
思路:DFS模板题,注意马可以跳8个方向,DFS是否回溯。
代码如下:
#include<cstdio>
#include<iostream>
using namespace std;
int vis[20][20]={0};
int xx[]={1,1,2,2,-1,-1,-2,-2};
int yy[]={-2,2,1,-1,2,-2,1,-1};
int sum;
int n,m,x,y;
void DFS(int x,int y,int count){
if(count==n*m){
sum++;
return ;
}
for(int i=0;i<8;i++){
int tempx=x+xx[i];
int tempy=y+yy[i];
if(tempx>=0 && tempy>=0 && tempx<n && tempy<m && vis[tempx][tempy]==0){
vis[tempx][tempy]=1;
DFS(tempx,tempy,count+1);
vis[tempx][tempy]=0;
}
}
return;
}
int main(){
int t;
cin>>t;
while(t--){
cin>>n>>m>>x>>y;
vis[x][y]=1;
sum=0;
DFS(x,y,1);
cout<<sum<<endl;
}
return 0;
}