啊哈磊_编程从这里起步

标题: [算法]BFS-写的比较复杂的版本 [打印本页]

作者: 啊哈磊 时间: 2013-2-20 20:49
标题: [算法]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]

作者: 创世菌 时间: 2018-3-3 17:48
这样就不需要自定义函数了……

欢迎光临啊哈磊_编程从这里起步 (https://bbs.codeaha.com/)