请算法高手帮忙。

Question

本人现在在写一个小游戏，遇到了一个最短路径的问题。
有如下一张地图数组：22220020
21010101
20000000
01012101
00021212
20220202
12101012
00000222其中，2表示通路，0表示怪物，1表示墙。
2可通过，0被打死后可通过（即变成了2），1不可通过。
现在，人可能处于地图中的任何一个“2”处，怎样设计一个算法，得到离人最近的可以达到的怪物（即通过的路径都是“2”）？

Answer 1

很简单
for （int i=0; i<8;i++)
{
   for (int j=0; j<8; j++)
   {
      if (a[i][j] == 0)
         return i;
      else if (a[i][j] == 1)
         break;
      else
         conitue;
   }
}

Answer 2

A*算法我大致看了下，很复杂，而且和我的要求不大一致，它是已知目的地的搜索算法，而我并没有明确的目的地。goodboywsd的算法并不能得到最近的怪物吧？

Answer 3

以点[i][j]为根构造树，递归广度遍历所有相邻点，需要检查是否已遍历过。
如果要求效率，可以用数组或链表只记录当前层的节点，用bool数组记录是否访问过。

Answer 4

http://drew.nease.net/algorithm/shortpath.htm
其实也就是这里说的Dijkstra算法，用Open Close。
你的动态目标的确不能用A*。

Answer 5

Dijkstra算法,参考一下图论相关书.

Answer 6

to goodboyws(深夜不眠者)
“人可能处于地图中的任何一个“2”处”，你的代码只是找最左边的一个怪物罢了。

Answer 7

呵呵，这样得到的是人处于地图起点时，最近的怪物
for （int j=0; j<8;j++)
{
   for (int i=0; i<8; i++)
   {
      if (a[i][j] == 0)
         return i;
      else if (a[i][j] == 1)
         break;
      else
         conitue;
   }
}
按照楼主的需求，只要考虑本人的位置就可以了，可能有些麻烦，变化也不大

Answer 8

呵呵，还是谢谢 goodboyws 。我最终采用lanphaday所说的dijkstra算法。谢谢大家，谢谢热心的兄弟们。