AcWing 1116. 马走日
原题链接
简单
作者:
一抹斜阳
,
2020-07-18 11:28:21
,
所有人可见
,
阅读 433
#include <iostream>
using namespace std;
int dx[8] = {2,1,-1,-2,-2,-1,1,2};
int dy[8] = {1,2,2,1,-1,-2,-2,-1};
const int N = 10;
bool st[N][N];
int res; //求走过的点数
int n,m,x,y,t;
int count; //求路线数
void dfs();
int main(){
cin>>t;
while(t--){
for(int i = 0;i< n;i++)
for(int j = 0;j<m;j++)
st[i][j] = false;
scanf("%d%d%d%d",&n,&m,&x,&y);
st[x][y] = true;
res = 1;
count = 0;
dfs();
cout<<count<<endl;
}
return 0;
}
void dfs(){
if(res == n*m){
count++;
return;
}
for(int i = 0;i<8;i++){
if(x + dx[i] >= 0 && x + dx[i] <= n-1 && y + dy[i] >= 0 && y + dy[i] <= m-1 && !st[x+dx[i]][y+dy[i]] ){
st[x+dx[i]][y+dy[i]] = true;
x = x + dx[i];
y = y + dy[i];
res++;
dfs();
res--;
y = y - dy[i];
x = x - dx[i];
st[x+dx[i]][y+dy[i]] = false;
}
}
}