搜索与回溯：马走日

川长思鸟来 2024-04-19 12:22 67阅读 0赞

### 1219：马走日 ###

时间限制: 1000 ms 内存限制: 65536 KB  
提交数: 5841 通过数: 3024

### 【题目描述】 ###

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

请编写一段程序，给定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<cstring>
    using namespace std;
    int fx[8] = {1,1,2,2,-1,-1,-2,-2};
    int fy[8] = {2,-2,1,-1,2,-2,1,-1};
    int ans,t,n,m,sx,sy;
    bool visited[101][101];
    void dfs(int x,int y,int tot)
    {
    	if(tot == n*m) ans++;//到达终点方案数+1
    	for(int i = 0; i < 8; ++i)
    	{
    		int xx = x+fx[i];
    		int yy = y+fy[i];
    		if(xx >= 0 && xx < n && yy >= 0 && yy < m && visited[xx][yy] == false)
    		{
    			visited[xx][yy] = true;
    			dfs(xx,yy,tot+1);
    			visited[xx][yy] = false;
    		}
    	 } 
    	  
    }
    int main()
    {
    	cin >> t;
    	while(t--)
    	{
    		memset(visited,false,sizeof(visited));//初始化所有的点都没有走过 
    		ans = 0;//每组测试数据开始之前结果要初始化 
    		cin >> n >> m >> sx >> sy;//n行m列，(x,y)为马的起始位置
    		visited[sx][sy] = true; 
    		dfs(sx,sy,1);
    		cout << ans << endl; 
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，67人围观）

还没有评论，来说两句吧...

相关阅读

相关搜索与回溯：马走日

1219：马走日时间限制: 1000 ms 内存限制: 65536 KB 提交数: 5841 通过数: 3024 【题目描述】马在中国象棋以日字...

川长思鸟来/ 2024年04月19日 12:22/ 0 赞/ 68 阅读

相关搜索与回溯：棋盘问题

1217：棋盘问题时间限制: 1000 ms 内存限制: 65536 KB 提交数: 5754 通过数: 2662 【题目描述】在一个给定形状的...

墨蓝/ 2024年04月19日 10:22/ 0 赞/ 82 阅读

相关搜索与回溯：迷宫

1215：迷宫时间限制: 1000 ms 内存限制: 65536 KB 提交数: 14993 通过数: 4360 【题目描述】一天Extense...

秒速五厘米/ 2024年04月19日 08:49/ 0 赞/ 92 阅读

相关搜索与回溯算法:LETTERS

1212：LETTERS 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 9638 通过数: 4193 【题目描述】给出一个r...

秒速五厘米/ 2024年04月19日 08:34/ 0 赞/ 97 阅读

相关 DFS之搜索顺序 AcWing 1116. 马走日

DFS之搜索顺序 AcWing 1116. 马走日原题链接 [AcWing 1116. 马走日][AcWing 1116.] 算法标签 DFS 思路

谁践踏了优雅/ 2024年04月07日 10:29/ 0 赞/ 72 阅读

相关搜索与回溯算法

前言搜索与回溯算法是计算机解题中的常用的算法基本思想： > 为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步

灰太狼/ 2022年12月27日 07:25/ 0 赞/ 195 阅读

相关数据结构-马走日的解法

【题目来自灰灰考研】（2018上海交通大学上机题）（2017华中科技大学上机题）假设国际象棋棋盘有5\5共25个格子。设计一个程序，使棋子从初始位置（如图）开始跳马，需

柔情只为你懂/ 2022年05月19日 06:46/ 0 赞/ 186 阅读

相关搜索与回溯算法

> 为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。一、前

快来打我*/ 2021年09月29日 00:12/ 0 赞/ 380 阅读

相关象棋马走日步数计算流程图

[象棋马走日正解判定表实现步数计算 ][Link 1] http://blog.csdn.net/number1killer/article/details/792144

布满荆棘的人生/ 2021年09月26日 11:56/ 0 赞/ 790 阅读

相关象棋马走日UML类图

![Center][] [象棋马走日正解判定表实现步数计算][Link 1] http://blog.csdn.net/number1killer/article/de

浅浅的花香味﹌/ 2021年09月26日 11:50/ 0 赞/ 351 阅读