[算法]BFS-写的比较复杂的版本

啊哈磊

[算法]BFS-写的比较复杂的版本
简单的版本，请见算法栏目
测试数据：
3 3
0 0 1
0 1 0
0 0 0
1 1
3 3

输出：
4

[code=Cpp width=740px]
#include <stdio.h>
struct note
{
    int x;
    int y;
    int f;
    int s;
};
struct note que[101];
int a[11][11],book[11][11]={0};


int main()
{
    int i,j,x1,x2,y1,y2,n,m;
    int tx,ty,top,bottom;
   
    scanf("%d %d",&n,&m);   
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            scanf("%d",&a[j]);
    scanf("%d %d",&x1,&y1);
    scanf("%d %d",&x2,&y2);         
   
   
    top=1;
    bottom=0;
   
    bottom++;
    que[bottom].x=x1;
    que[bottom].y=y1;
    book[x1][y1]=1;
   
    //right down left up
    while(top<=bottom)
    {
        //right
        tx=que[top].x;
        ty=que[top].y+1;
        if(tx>=1 && tx<=n && ty>=1 && ty<=m)
        if(a[tx][ty]==0 && book[tx][ty]==0)
        {
            bottom++;
            que[bottom].x=tx;
            que[bottom].y=ty;
            que[bottom].f=top;
            que[bottom].s=que[top].s+1;
            book[tx][ty]=1;
            if(tx==x2 && ty==y2)
                break;
        }
        
        //down
        tx=que[top].x+1;
        ty=que[top].y;
        if(tx>=1 && tx<=n && ty>=1 && ty<=m)
        if(a[tx][ty]==0 && book[tx][ty]==0)
        {
            bottom++;
            que[bottom].x=tx;
            que[bottom].y=ty;
            que[bottom].f=top;
            que[bottom].s=que[top].s+1;
            book[tx][ty]=1;
            if(tx==x2 && ty==y2)
                break;
        }
        
        //left
        tx=que[top].x;
        ty=que[top].y-1;
        if(tx>=1 && tx<=n && ty>=1 && ty<=m)
        if(a[tx][ty]==0 && book[tx][ty]==0)
        {
            bottom++;
            que[bottom].x=tx;
            que[bottom].y=ty;
            que[bottom].f=top;
            que[bottom].s=que[top].s+1;
            book[tx][ty]=1;
            if(tx==x2 && ty==y2)
                break;
        }
        
        //up
        tx=que[top].x-1;
        ty=que[top].y;
        if(tx>=1 && tx<=n && ty>=1 && ty<=m)
        if(a[tx][ty]==0 && book[tx][ty]==0)
        {
            bottom++;
            que[bottom].x=tx;
            que[bottom].y=ty;
            que[bottom].f=top;
            que[bottom].s=que[top].s+1;
            book[tx][ty]=1;
            if(tx==x2 && ty==y2)
                break;
        }
        
        top++;//很重要  
    }
   
    if(que[bottom].x==x2 && que[bottom].y==y2)
        printf("%d",que[bottom].s);
    else
        printf("-1");
   
   
    getchar();
    getchar();
    return 0;
}
[/code]

创世菌

这样就不需要自定义函数了……