马踏棋盘--dfs
2024-10-09 14:03:19
【问题描述】关于马踏棋盘的基本过程:国际象棋的棋盘为 8*8 的方格棋盘。现将"马"放在任意指定的方格中,按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次,最终使得"马"走遍棋盘的64个方格。
输入一个n,表示大小为n x n的棋盘
输出马走遍棋盘所有格子的顺序和不同的走法数量
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int vis[][];
int cnt = , n, m;
int inbord(int x, int y)//判断是否在棋盘上
{
if (x >= && x<n&&y >= && y<m)
return ;
else
return ;
}
void dfs(int x, int y, int ans)
{
if (inbord(x, y) && !vis[x][y])
{
ans++;
vis[x][y] = ans;
if (ans == n * m)
{
cnt++;
printf("#case %d\n", cnt);
for (int i = ; i < n; i++)
{
for (int j = ; j < m; j++)
printf("%4d", vis[i][j]);
printf("\n");
}
vis[x][y] = ;//回溯,遍历不同情况
return;
}
else//八个方向
{
dfs(x - , y - , ans);
dfs(x - , y + , ans);
dfs(x + , y - , ans);
dfs(x + , y + , ans);
dfs(x + , y - , ans);
dfs(x + , y + , ans);
dfs(x - , y + , ans);
dfs(x - , y - , ans);
vis[x][y] = ;//回溯,一定要走完整个棋盘,要尝试不同方向
}
}
else
return;
}
int main()
{
scanf("%d%d", &n, &m);
memset(vis, , sizeof(vis));
dfs(, , );
return ;
}
最新文章
- 【MVVM】模型认识理解,
- <;把时间当做朋友>;读书笔记
- SqlCommand执行带GO的SQL脚本文件
- CentOS 6.5安装 ASM lib
- UOJ30——【CF Round #278】Tourists
- C# 根据IP地址获取城市
- JS删除数组条目中重复的条目
- LTE Module User Documentation(翻译5)——Mobility Model with Buildings
- 【题解】【排列组合】【回溯】【Leetcode】Gray Code
- android之location01
- 支付宝修改回调地址后 issign=false
- **json_encode:让Json更懂中文(JSON_UNESCAPED_UNICODE)
- IP地址理解_IP地址=网络地址+主机地址,但是具体前面多少是网络地址看题目说明
- 如何实现MySQL随机查询数据与MySQL随机更新数据?
- HDU 4916 Count on the path
- 再次深入 C# Attribute
- ubuntu下mysql二进制包安装
- encodeURI与decodeURI
- 【SSD,FIO,SAS选择的一些小结】SSD,FIO,SAS选择的一些小结
- iOS——系统提供的dispatch方法