※ 引述《soheadsome (師大狗鼻哥)》之銘言：
: 不好意思 這算半個作業文
: 題目的內容大概是
: 一個棋盤會給定起點和終點
: 然後棋盤上每一格都會有值
: 求起點到終點的所經過的最小值
: 我大概知道要用BFS來解決
: 但我想到說起點和終點會不固定
: 如果我剛好這次的iterate有兩個以上相同的值
: 我應該是依貪婪的方式 選擇離終點最近的
: 但我想是該直接去量兩者之間的距離
: 還是應該直接選方位呢?
: (若終點在左上 我應當選這次可走的最左或最上方為主)
: 這邊卡了滿久
: 希望有大大能幫忙解惑 謝謝
Here are some quick ideas..
1. You need to assume the weights in each grid are all
positive. Otherwise you may have a 'negative' loop
and the result will not be reasonable.
2. Then, the chess board can be represented as a graph.
More preceisely, it will be a grid.
3. It will become a classical problem of Dynamic programming (DP)..
Read Dijkstra algorithm..