※ 引述《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..