[算法]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]
|