题目

题面

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

请编写一段程序，给定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

思路

因为要求马遍历棋盘的途径总数，我们可以很容易的想到使用dfs来解决这个问题。如何判断是否为填满了整个棋盘就要想到如果能遍历，那一定是走了n*m个点，于是在设计dfs的时候设计为void dfs(int x, int y, int step)，其中step为当前走了多少步。

代码

 1  1 #include <iostream>

 2  2 #include <algorithm>

 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[x][y] = 1;

42 42         dfs(x, y, 0);

43 43         cout << ans << endl;

44 44     }

45 45     return 0;

46 46 }

巴特西

2022GDUT寒训专题一C题

题目

题面

输入格式

输出格式

思路

代码

最新文章

热门文章