【NOI 8465】马走日 深搜DFS

                                                  8465:马走日

描述

马在中国象棋以日字形规则移动。

请编写一段程序，给定n*m大小的棋盘，以及马的初始位置(x，y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。

输入

第一行为整数T(T < 10)，表示测试数据组数。
每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标n,m,x,y。(0<=x<=n-1,0<=y<=m-1, m < 10, n < 10)

输出

每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0为无法遍历一次。

样例输入

1
5 4 0 0

样例输出

32

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
#define closeio std::ios::sync_with_stdio(false)

int d[8][2]={{1,2},{1,-2},{-1,-2},{-1,2},{2,1},{2,-1},{-2,1},{-2,-1}};    //马能走的8个方向 
int vis[10][10],n,m,maxn,sum;

void dfs(int x,int y,int num)
{
	if(num>=maxn)			//num>=maxn表示走完了棋盘上全部的点 
		sum++;
	for(int i=0;i<8;i++)
	{
		int tx=x+d[i][0];
		int ty=y+d[i][1];
		if(tx>=0&&tx<n&&ty>=0&&ty<m&&vis[tx][ty]==0)	//判断该点在棋盘内且未被走过 
		{
			vis[tx][ty]=1;
			dfs(tx,ty,num+1);
			vis[tx][ty]=0;
		}
	}
}

int main()
{
	int t,x,y,i,j;
	cin>>t;
	while(t--)
	{
		mem(vis,0);				//数组初始化
		cin>>n>>m>>x>>y;
		vis[x][y]=1;
		maxn=n*m;				//棋盘共有maxn个点 
		sum=0;
		dfs(x,y,1);				
		cout<<sum<<endl;
	}
	return 0;
}