Fw: [問題] 西洋棋騎士問題(最短路徑) bleed1979 PTT批踢踢實業坊

Fw: [問題] 西洋棋騎士問題(最短路徑)

作者: bleed1979 (十三) 2013-06-16 17:02:57

※ [本文轉錄自 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
表示所在位置在@號位置
目標位置在#號位置

作者: ianweng509 (嗡嗡) 2013-06-13 07:51:00

忘了說上面的change函數是將輸入的char轉換成座標!

作者: kiedveian (極地之星光) 2013-06-13 07:54:00

函式加個參數(目前最小值)，新找到的小於它才return效能可能不怎麼好就是了…

作者: ianweng509 (嗡嗡) 2013-06-13 07:57:00

可是一定要有個初始值這樣第一次不是不管怎樣都會小於嗎@@?因為我是讓他在flag陣列裡面的值++ 最後只要從0~7印出第一個非0的數

作者: kiedveian (極地之星光) 2013-06-13 07:59:00

無視我上面寫的，在for前面加個變數比較快

作者: tobygameac (toby) 2013-06-13 08:15:00

BFS

作者: ianweng509 (嗡嗡) 2013-06-13 08:19:00

樓上您說的我有google到但我不是資工系的我真的看不懂這個演算法在幹嘛以及如何運用在我的問題上ˊˋ

作者: tobygameac (toby) 2013-06-13 08:33:00

把每個點都想成一個狀態每到一個狀態就把所有能走還沒走的狀態在加入queue裡面可以想成是暴力窮舉，但過濾掉已走過的http://codepad.org/uCfFy790

作者: a88258850 2013-06-13 11:21:00

BFS的概念接近水波擴散的感覺

作者: tjjh89017 (伊達政宗) 2013-06-13 13:29:00

這題應該就是用BFS 原PO一開始應該是用DFS吧

作者: ianweng509 (嗡嗡) 2013-06-13 19:47:00

感謝各位！另外請教DFS 是什麼意思？

作者: janice001 (真理) 2013-06-13 20:35:00

DFS 深度優先搜尋 BFS 廣度優先搜尋 google it

作者: DarkPrincex (DP) 2013-06-13 23:54:00

第64行~第66行那裡，你找到一組解就直接return了所以才會有找到一組幾就跳開的樣子

作者: amozartea (單車單) 2013-06-15 02:47:00

越走應越近變遠的去掉

繼續閱讀

[情報] Competitive Programming 1/edplover [閒聊] 有人在解project euler上的題目嗎WaiTingKuo Fw: [問卦] 有沒有數學沒有標準答案的八卦？eternity1357 Re: [問題] Hamiltonian Circuit問題ferng1021 [問題] Hamiltonian Circuit問題FRAXIS [請益] 演算法作業的問題 (max weight subgraph)soheadsome [問題] UVa 838s89162504 [問題] ICPC 4000paae0226 Re: [問題] Google Interview Question (1)Leon Re: [問題] UVA 11294 weddingdreamoon