noi 8465 马走日
2024-10-11 08:58:19
8465:马走日
- 总时间限制:
- 1000ms
- 内存限制:
- 1024kB
- 描述
-
马在中国象棋以日字形规则移动。
请编写一段程序,给定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
分析:
方案数:每到一个状态,都有不同的8个方案,但是,一步只能选择一个状态去转移,这时候就是DFS回溯的时候了。
#include <bits/stdc++.h>
using namespace std; int n,m; bool vis[][]; int dr[] = {-,-,-,-,,,,};
int dc[] = {-,-,,,,,-,-}; int ans = ; void dfs(int r,int c,int cnt) {
if(r<||c<||r>=n||c>=m||vis[r][c]) return ; if(cnt==n*m) {
ans ++;
return ;
}
vis[r][c] = true;
for(int i=;i<;i++)
dfs(r+dr[i],c+dc[i],cnt+);
vis[r][c] = false;
} int main()
{
int t;
scanf("%d",&t);
while(t--) {
ans = ;
scanf("%d%d",&n,&m);
int r,c;
scanf("%d%d",&r,&c);
dfs(r,c,);
printf("%d\n",ans);
} return ;
}
最新文章
- perl 如何匹配ASCII码以及ASCII码转换
- iOS可执行文件瘦身方法
- SqlServer数据类型
- DEDECMS之二 如何修改模板页
- java 反取字符串
- Rest接口测试,巧用firebug插件
- CcTalk (网络协议)(转)
- 精通D3.js学习笔记(1)基础的函数
- FastDFS的安装配置
- new Date()的数据类型的问题
- 【POJ2777】Count Color(线段树)
- 排列与组合的C语言实现
- MySQL针对Swap分区的运维注意点
- php读取excel时间42930转化为时间然后正则验证时间是否通过
- DELPHI中自定义消息的发送和接收
- 并发编程(二):全视角解析volatile
- PostgreSQL远程连接配置
- textbox显示定位到最后一行(最新一行)
- 学习OpenCV——SVM
- AspNet.WebAPI.OData.ODataPQ实现WebAPI的分页查询服务-(个人拙笔)(转)