作者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