回上層
Disp BBS
看板 Prob_Solve
作者 bleed1979 (十三)
標題 Fw: [問題] 西洋棋騎士問題(最短路徑)
時間 Sun Jun 16 17:02:57 2013

※ [本文轉錄自 C_and_CPP 看板 #1HkGZd0J ]

看板 C_and_CPP
作者 ianweng509 (嗡嗡)
標題 [問題] 西洋棋騎士問題(最短路徑)
時間 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
C code - 101 lines - codepad
 

補充說明(Supplement)：

這是今天要交的作業，來不及交沒關係

我還是很想知道我該怎麼修改才會比較好

有想過乾脆重寫改成暴力破解

但是想說都寫這麼久了....

感謝各位了!!


--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.34.137.79
→ ianweng509:忘了說 上面的change函數是將輸入的char轉換成座標!1F 06/13 07:51
→ kiedveian:函式加個參數(目前最小值)，新找到的小於它才return
效能可能不怎麼好就是了…2F 06/13 07:54
→ ianweng509:可是一定要有個初始值 這樣第一次不是不管怎樣都會小於嗎@@?
因為我是讓他在flag陣列裡面的值++ 最後只要從0~7印出第一個非0的數4F 06/13 07:57
→ kiedveian:無視我上面寫的，在for前面加個變數比較快8F 06/13 07:59
→ tobygameac:BFS9F 06/13 08:15
→ ianweng509:樓上您說的我有google到 但我不是資工系的我真的看不懂這個演算法在幹嘛 以及如何運用在我的問題上ˊˋ10F 06/13 08:19
→ tobygameac:把每個點都想成一個狀態
每到一個狀態就把所有能走還沒走的狀態在加入queue裡面可以想成是暴力窮舉，但過濾掉已走過的
http://codepad.org/uCfFy79012F 06/13 08:33
C++ code - 52 lines - codepad
 
→ a88258850:BFS的概念接近水波擴散的感覺16F 06/13 11:21
→ tjjh89017:這題應該就是用BFS  原PO一開始應該是用DFS吧17F 06/13 13:29
→ ianweng509:感謝各位！另外請教DFS 是什麼意思？18F 06/13 19:47
→ janice001:DFS 深度優先搜尋 BFS 廣度優先搜尋 google it19F 06/13 20:35
推 DarkPrincex:第64行~第66行那裡，你找到一組解就直接return了
所以才會有找到一組幾就跳開的樣子20F 06/13 23:54
推 amozartea:越走應越近 變遠的去掉22F 06/15 02:47

※ 發信站: 批踢踢實業坊(ptt.cc)
※ 轉錄者: bleed1979 (114.32.177.97), 時間: 06/16/2013 17:02:57

--
作者 bleed1979 的最新發文:
  • +8 [推坑] 緯德科技 - Soft_Job 板
    作者: bleed1979 220.135.203.156 (台灣) 2014-12-28 12:10:59
    ＠公司名稱：（請盡量寫正確的全名） 緯德科技股份有限公司 (TechLink Corporation) ＠工作地點：（約略就好～） 依照客戶所在位置而定。台北市內科，南軟都有可能。 ＠工時狀況：(不計 …
    14F 8推
  • +9 [請益] Google 面試流程 - Soft_Job 板
    作者: bleed1979 220.135.203.156 (台灣) 2014-12-01 06:41:24
    安，先搜過文。 想請教曾經面試Google矽谷那間的板友，其面試流程為何？ ...................... 2009 年 分隔線 ....................... 很榮幸地 …
    25F 9推
  • +2 Re: [心情] 前輩拒絕導入任何其他工具.... - Soft_Job 板
    作者: bleed1979 220.135.203.156 (台灣) 2014-05-18 00:16:49
    我的看法： 新語言/語法在於專案的進行程度。 新工具在於部門員工的熟悉程度。 專案如果是從無到有，新語言/語法有何不對？ 況且學JSP會不知道掛EL Ignore false，寫JSTL。 我很懷疑這 …
    3F 2推
  • +15 [閒聊] 如果對岸的軟體高手真的來台搶飯碗 - Soft_Job 板
    作者: bleed1979 220.135.203.156 (台灣) 2014-04-07 05:47:34
    先說， 當有人以問句問我問題，我的回答是偏英文作風。 Yes/No. Because ... ... blabla ... ... 我會先回答綜合我意見的二分法答案，才說明我的理由。 ======== …
    54F 15推
  • +2 Fw: [問題] 西洋棋騎士問題(最短路徑) - Prob_Solve 板
    作者: bleed1979 114.34.137.79 (台灣) 2013-06-16 17:02:57
    開發平台(Platform): (Ex: VC++, GCC, Linux, ...) Dev C++ 問題(Question)： 輸入所在以及目標座標後，求最短路徑的的步數 我用遞迴寫，但程式一旦找 …
    22F 2推
(bleed1979.): Fw: [問題] 西洋棋騎士問題(最短路徑) - dinos板