上次卧龙孔明给我了一个求迷宫最短步数的代码，我研究了一下，加了点注释，发出来大家看看。
这个代码的算法我看懂了，自己画了一个10*10的迷宫，在纸上画了半天，得到的结果果然是最短的。
但我真的不理解，这个算法是如何被发现的。

孔明给了我这么一句话：用很容易想到的DP就可以将复杂度搞到O(N^3)
再优化一下可是使之降到O(N^2)
对于障碍物较稀疏的迷宫问题使用dfs可以更快的出解，对于障碍物密集的迷宫问题使用bfs也可以快速出解

很容易想到。。。。。真的不容易，请高手们指点一下我（不一定要完全的答案），这个算法的思路是什么。
应该是一步一步推导出这个算法的吧。推导的过程或者起点是什么。

先谢谢大家。
2楼帖代码

[[it] 本帖最后由 SNAKEQX 于 2008-4-19 11:05 编辑 [/it]]

//////////////////////////////////////////////////
// Find the shortest step number, no path to show
// left top is the end point
// right bottom is the start point
//
//           !!!!!!Warning!!!!!!
// The maze in sos.in must have an answer
// Otherwise the the prog. will always loop
//////////////////////////////////////////////////

#include<stdio.h>

int main(void)
{
    int i,j,k;
    int n;        // map matrix n*n
    int x[30][30];// max map buff 30*30
    int t,c;
    FILE *in,*out;
   
    in=fopen("sos.in","r");
    out=fopen("sos.out","w");
   
    fscanf(in,"%d",&n);// first line in sos.in to n
                       // raw data array sequence is form 1 to n
                       // but in C/C++, array index starts with 0
   
    //Ini the map from sos.in
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
      {
        fscanf(in,"%d",&x[i][j]);
        if(x[i][j]==1) x[i][j]=-1; //wall  -1
        else x[i][j]=1000;         // walk path 1000.
      }                            // why 1000? bcs 30*30==900 <1000
      
    x[0][0]=1;// set the first step number,
              // not step sequence in the maze! It's end point.
    c=n-1;    // reset the array sequence from 0 to n-1
   
    /////////////////////////////////////////////////
    //                 Algorithm:                  
    // An Iterator goes from up to down,           
    // and at the same time left to right in the maze.         
    // If the neighbor position can be walked      
    // and the {value+1} is smaller than self,     
    // set the self to {value+1} .                 
    // When the Iterator goes to the start point   
    // (x[n-1,n-1]),the value of it               
    // is the answer to the ques.  .               
    /////////////////////////////////////////////////
    while(x[c][c]==1000)
    {
      for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
          // if not the most left, left
          if(i>0)
            if(x[i-1][j]!=-1)
              if((t=x[i-1][j]+1)<x[i][j])
                x[i][j]=t;

          // if not the most right, right
          if(i<c)
            if(x[i+1][j]!=-1)
              if((t=x[i+1][j]+1)<x[i][j])
                x[i][j]=t;

          // if not the most up, up
          if(j>0)
            if(x[i][j-1]!=-1)
              if((t=x[i][j-1]+1)<x[i][j])
                x[i][j]=t;

          // if not the most down, down
          if(j<c)
            if(x[i][j+1]!=-1)
              if((t=x[i][j+1]+1)<x[i][j])
                x[i][j]=t;
        }
    }
   
    //Output the shortest steps
    fprintf(out,"%d\n",x[c][c]);
   
    //discard opened files
    fclose(in);
    fclose(out);
   
    return 0;
}

这个，这个是孔明给我的啊，我看了很长时间啊。。。另外BFS是什么？
还有能不能给个思路阿。。。。。

一下是baidu搜到的。。。。
       广度优先搜索,即BFS(Breadth First Search),常常与深度优先搜索并列提及。这是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的近邻加入搜索队列（而深度优先搜索则是栈），循环搜索过程直到队列为空。
        在深度优先搜索中，深度越大的结点越先得到扩展。如果把它改为深度越小的结点越先得到扩展，就是广度优先搜索法。
        常见应用：无权最短路

似乎这个迷宫问题就是无权的吧，因为只要是路就能走，可以正走也可以反走。

可是算法的本质我还是不理解。

原题是自娱自乐，写了个2D走迷宫的代码，用的是进站出站遍历整个迷宫的方法，但不是最短路径，孔明给了我一个最短路径的方法，我看了一段时间，觉得挺有意思，但是不知道这个算法是怎么来的。所以想问问。

综上，题目就是2d迷宫从指定起点到指定终点的最短路径。

另外，此帖好像和我没多大关系啊，难道是错觉？

[[it] 本帖最后由 SNAKEQX 于 2008-4-19 09:46 编辑 [/it]]

d[x][y]=max{ d[x+1][y] , d[x-1][y], d[x][y-1], d[x][y+1] };？？？
不是min????
d代表什么呢？

那请问一下，为什么是由终点到起点的反推呢？
还有先判断上下和先判断左右有什么讲究呢？

还是正根本和终点起点无关，只是正巧终点在x[0][0]的位置。