2022GDUT寒训专题一C题
题目
题面
马在中国象棋以日字形规则移动。
请编写一段程序，给定n×m大小的棋盘，以及马的初始位置 (x, y)，要求不能重复经过棋盘上的同一个点，计算马可以有多少途径遍历棋盘上的所有点。
输入格式
第一行为整数 T(T < 10)，表示测试数据组数。 每一组测试数据包含一行，为四个整数，分别为棋盘的大小以及初始位置坐标 n,m,x,y(0≤x≤n−1,0≤y≤m−1,m<10,n<10)。
Sample Input
1
5 4 0 0
输出格式
每组测试数据包含一行，为一个整数，表示马能遍历棋盘的途径总数，0 为无法遍历一次。
Sample Output
32
思路
因为要求马遍历棋盘的途径总数，我们可以很容易的想到使用dfs来解决这个问题。如何判断是否为填满了整个棋盘就要想到如果能遍历，那一定是走了n*m个点，于是在设计dfs的时候设计为void dfs(int x, int y, int step)，其中step为当前走了多少步。
代码
1 1 #include
2 2 #include
3 3 using namespace std;
4 4 int n, m, x, y, ans;
5 5 int vis[20][20];
6 6 int a[8][2] = {{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
7 7 //顺便记录步数
8 8 void dfs(int x, int y, int step)
9 9 {
10 10 //其实就是当且仅当step为n*m-1步的时候即为填满了整个棋盘
11 11 if(step == n*m-1)
12 12 {
13 13 ans++;
14 14 return;
15 15 }
16 16 for(int i = 0;i < 8;++i)
17 17 {
18 18 //然后正常遍历就行了
19 19 int xx = x+a[i][0], yy = y+a[i][1];
20 20 //如果一直进不去自然会return的
21 21 if(xx >= 0 && xx <= n-1 && yy >= 0 && yy <= m-1 && vis[xx][yy] == 0)
22 22 {
23 23 vis[xx][yy] = 1;
24 24 dfs(xx, yy, step+1);
25 25 vis[xx][yy] = 0;
26 26 }
27 27 }
28 28 }
29 29
30 30 int main()
31 31 {
32 32 int t;cin >> t;
33 33 while(t--)
34 34 {
35 35 //多组数据要记得初始化
36 36 for(int i = 0;i < 20;++i)
37 37 for(int j = 0;j < 20;++j)
38 38 vis[i][j] = 0;
39 39 cin >> n >> m >> x >> y;
40 40 ans = 0;
41 41 vis[y] = 1;
42 42 dfs(x, y, 0);
43 43 cout << ans << endl;
44 44 }
45 45 return 0;
46 46 }