2022GDUT寒训专题一C题
admin
撰写于 2022年 01月 22 日

题目

题面

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

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

输入格式

第一行为整数 T(T < 10),表示测试数据组数。 每一组测试数据包含一行,为四个整数,分别为棋盘的大小以及初始位置坐标 n,m,x,y(0≤xn−1,0≤ym−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 }

2022GDUT寒训专题一C题的

2022GDUT寒训专题一C题

题目

题面

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

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

输入格式

第一行为整数 T(T < 10),表示测试数据组数。 每一组测试数据包含一行,为四个整数,分别为棋盘的大小以及初始位置坐标 n,m,x,y(0≤xn−1,0≤ym−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 }

2022GDUT寒训专题一C题的

赞 (0)

猜您想看

评论区(暂无评论)

这里空空如也,快来评论吧~

我要评论