poj2488 A Knight’s Journey

poj2488 A Knight’s Journey

http://poj.org/problem?id=2488

 

题目大意:骑士厌倦了一遍又一遍地看到同样的黑白方块,于是决定去旅行。

世界各地。当一个骑士移动时,他走的是“日”字。骑士的世界是他赖以生存的棋盘。我们的骑士生活在一个棋盘上,它的面积比普通的8 * 8板要小,但它仍然是矩形的。你能帮这个冒险的骑士制定旅行计划吗? 找到一条路,这样骑士每一次都能到每一个广场。骑士可以在棋盘的任何方格上开始和结束。输入从第一行的正整数n开始。下面的行包含n个测试用例。每个测试用例由一个带有两个正整数p和q的单行组成,其中1 <= p * q <= 26。这表示一个p * q棋盘,其中p描述了多少个不同的数1,…p存在,q描述存在多少个不同的字母。这些是拉丁字母表中的第一个q字母:A,…每个场景的输出从包含“Scenario #i:”的一行开始,其中i是从1开始的场景的数量。然后打印一行一行,其中包含了字母顺序的第一路径,它访问棋盘上的所有方块,然后是空行。通过将访问的方块的名称连接起来,可以在一行中给出路径。每个方名称由大写字母和数字组成。

如果不存在这样的路径,那么您应该在一行上输出impossible的内容。

 

也就是说横坐标时是字母(向右为正),纵坐标是数字(向下为正),骑士需要走完全图的方格,并找出包含了字母顺序的第一条路径,那么这就暗示了骑士的起点坐标一定是A1,只有是按字母排序第一个一定是A1。骑士走的是“日”字,那么根据字母排序骑士的横坐标和纵坐标减少或增加的遍历顺序是8个方向(-2,-1)(-2,1)(-1,-2)(-1,2)(1,-2)(1,2)(2,-1)(2,1),这样的遍历顺序,得到的第一条路径一定是按字母顺序的路径。

 

算法思想:回溯法,问题的解空间树是一颗八叉树,分别对应八个方向,设置相应的剪枝函数,1)如果出界,舍弃相应子树;2)如果找到了一条路径(一定是按字母排序的路径),用一个isSoluted记录,如果问题解决,则减去相应子树;3)我们可以用visited[ ][ ]记录该方格被访问,减去相应子树(重复走回路),并在回溯时设为未访问。

 1 #include <cstring>//使用memset()  2 #include <iostream>  3 using namespace std;  4 //按字典排序的行走方向 8叉树  5 const int dx[8] = { -2, -2, -1, -1, 1, 1, 2, 2 };  6 const int dy[8] = { -1, 1, -2, 2, -2, 2, -1, 1 };  7 const int N = 27;  8 bool visited[N][N];//判断方格是否被访问  9 struct step { //走路的记录 10 char x, y; 11 }; 12 step path[N];//记录路径的 13 bool isSoluted;//能否走通 14 int cases, p, q;//记录案例数,p行123... q列ABC... 15 void Backtrade(int x, int y, int t)//x 和 y 为当前坐标 t为深度 16 { 17 path[t].x = x + 'A' - 1; //转为 char 记录走的路径 18 path[t].y = y + '0'; 19 if (t == p * q)//如果有一条路走完全部 则可解 直接退出回溯 20  { 21 isSoluted = true; 22 return; 23  } 24 for (int i = 0; i < 8; i++) 25  { 26 int nx = x + dx[i]; 27 int ny = y + dy[i]; 28 //剪枝函数 出界 或 已访问过 或 问题已解决 不进入相应子树 29 if (0 < nx && nx <= q && 0 < ny && ny <= p&& !visited[nx][ny] && !isSoluted) 30  { 31 visited[nx][ny] = true; 32 Backtrade(nx, ny, t + 1); 33 visited[nx][ny] = false;//回溯时撤回标记 34  } 35  } 36 } 37 int main() 38 { 39 cin>>cases; 40 for (int c = 1; c <= cases; c++) 41  { 42 isSoluted = false; 43 cin >> p >> q; 44 memset(visited, false, sizeof(visited)); 45 visited[1][1] = true; //从第一个字典序起点开始走 46 Backtrade(1, 1, 1); 47 cout<<"Scenario #"<<c<<":"<<endl; 48 if (isSoluted) 49  { 50 for (int i = 1; i <= p * q; i++) 51 cout << path[i].x << path[i].y; 52 cout << endl; 53  } 54 else 55 cout<<"impossible"<<endl; 56 cout << endl; 57  } 58 return 0; 59 }

 

转载于:https://www.cnblogs.com/DA799422035/p/8994075.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/101680.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • webstorm永久激活码_最新在线免费激活

    (webstorm永久激活码)好多小伙伴总是说激活码老是失效,太麻烦,关注/收藏全栈君太难教程,2021永久激活的方法等着你。https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~S32PGH0SQB-eyJsaWNlbnNlSWQiOi…

  • http和https的优缺点,区别与工作原理

    http和https的优缺点,区别与工作原理

  • 群晖3617可以有几个网卡_解决黑群辉使用的几个问题

    群晖3617可以有几个网卡_解决黑群辉使用的几个问题本文帮助黑群辉刚上手的人,默认已经安装好黑群辉系统了哦。如果系统也还没有安装,那就要根据自己现有手上的设备搜索相应的安装教程了。相应文章很多,情况也不同,就不在这里说明了。一、启用视频缩略图和转码一般使用群辉的人肯定要用它来保存自己的照片和视频,所以这个功能一定要开启的。否则VS和photo中各种感叹号图。倒是不影响播放,但是预览和美观就很不方便了。目前最完美的解决方案是半洗白,可以开启视频缩略图…

  • 什么叫买单报关_代理报关和买单报关费用是一样的吗

    什么叫买单报关_代理报关和买单报关费用是一样的吗报关是指货物、行李和邮递物品、运输工具等在进出关境或国境时由所有人或其代理人向海关申报,交验规定的单据、证件,请求海关办理进出口的有关手续。我国海关规定报关时应交纳的单据、证件。有:进出口货物报关单、进出口货物许可证、商品检验证书、动植物检疫证书、食品卫生检验证书以及提货单、装货单、运单、发票、装箱单等。买单出口,其实就是没有出口权的工厂或SOHO通过买别的进出口公司的核销单,以该公司的名义进行外贸出口。买单出口所买的“单”主要是指核销单,但是卖单出口服务的公司除了提供核销单之外还需要提供与核销单抬头一

  • MacBook navicat15 激活码【2022.01最新】2022.02.25

    (MacBook navicat15 激活码)最近有小伙伴私信我,问我这边有没有免费的intellijIdea的激活码,然后我将全栈君台教程分享给他了。激活成功之后他一直表示感谢,哈哈~IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • 背包九讲——完全背包

    背包九讲——完全背包完全背包是01背包的加强版,先来看看《背包问题九讲》里是怎么描述这个问题的:题目有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。所属专栏:戳我访问再来看看《背包问题九讲》是怎么解决这个问题的:基本思路这个问题非常类似于01背包问题,所不同

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号