作者bleed1979 (十三)
看板Prob_Solve
标题Fw: [问题] 西洋棋骑士问题(最短路径)
时间Sun Jun 16 17:02:57 2013
※ [本文转录自 C_and_CPP 看板 #1HkGZd0J ]
作者: ianweng509 (嗡嗡) 看板: C_and_CPP
标题: [问题] 西洋棋骑士问题(最短路径)
时间: Thu Jun 13 07:48:53 2013
开发平台(Platform): (Ex: VC++, GCC, Linux, ...)
Dev C++
问题(Question)：
输入所在以及目标座标後，求最短路径的的步数
我用递回写，但程式一旦找到一条路径以後就会跳开
不会去试其他较快的步数
想不到该怎麽修改程式会比较好
喂入的资料(Input)：
C5 F5
表示所在位置在@号位置
目标位置在#号位置
------------------------
1
------------------------
2
------------------------
3
------------------------
4
------------------------
5 @ #
------------------------
6
------------------------
7
------------------------
8
------------------------
A B C D E F G H
预期的正确结果(Expected Output)：
能够输出上面例子应该为走3步 我的程式显示为7步
错误结果(Wrong Output)：
显示为7步
程式码(Code)：(请善用置底文网页, 记得排版)
http://codepad.org/WQxA0BEs
补充说明(Supplement)：
这是今天要交的作业，来不及交没关系
我还是很想知道我该怎麽修改才会比较好
有想过乾脆重写改成暴力破解
但是想说都写这麽久了....
感谢各位了!!
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 114.34.137.79
1F：→ ianweng509:忘了说 上面的change函数是将输入的char转换成座标! 06/13 07:51
2F：→ kiedveian:函式加个参数(目前最小值)，新找到的小於它才return 06/13 07:54
3F：→ kiedveian:效能可能不怎麽好就是了… 06/13 07:55
4F：→ ianweng509:可是一定要有个初始值 这样第一次不是不管怎样都会小於 06/13 07:57
5F：→ ianweng509:吗@@? 06/13 07:57
6F：→ ianweng509:因为我是让他在flag阵列里面的值++ 最後只要从0~7印出 06/13 07:58
7F：→ ianweng509:第一个非0的数 06/13 07:58
8F：→ kiedveian:无视我上面写的，在for前面加个变数比较快 06/13 07:59
9F：→ tobygameac:BFS 06/13 08:15
10F：→ ianweng509:楼上您说的我有google到 但我不是资工系的我真的看不懂 06/13 08:19
11F：→ ianweng509:这个演算法在干嘛 以及如何运用在我的问题上ˊˋ 06/13 08:19
12F：→ tobygameac:把每个点都想成一个状态 06/13 08:33
13F：→ tobygameac:每到一个状态就把所有能走还没走的状态在加入queue里面 06/13 08:34
14F：→ tobygameac:可以想成是暴力穷举，但过滤掉已走过的 06/13 08:45
16F：→ a88258850:BFS的概念接近水波扩散的感觉 06/13 11:21
17F：→ tjjh89017:这题应该就是用BFS 原PO一开始应该是用DFS吧 06/13 13:29
18F：→ ianweng509:感谢各位！另外请教DFS 是什麽意思？ 06/13 19:47
19F：→ janice001:DFS 深度优先搜寻 BFS 广度优先搜寻 google it 06/13 20:35
20F：推 DarkPrincex:第64行~第66行那里，你找到一组解就直接return了 06/13 23:54
21F：→ DarkPrincex:所以才会有找到一组几就跳开的样子 06/13 23:55
22F：推 amozartea:越走应越近 变远的去掉 06/15 02:47
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 转录者: bleed1979 (114.32.177.97), 时间: 06/16/2013 17:02:57