讨论 / 为毛输出都是1
sz136380243 2016-09-12 21:50:35
点我顶贴 收藏 删除
#include<stdio.h>

#include<stdlib.h>

int map[1001][1001],n,rear=0,front=0;

int xx[4]={0,0,1,-1};

int yy[4]={-1,1,0,0};

int BFS(int begin_i,int begin_j,int end_i,int end_j);

void Push(int x,int y,int distance);

struct point Pop();

struct point

{

int x,y;

int distance;

}p[100000];

int main()

{

int i,j;

int begin_i,begin_j,end_i,end_j;

char c;

scanf("%d",&n);getchar();

for(i=1;i<=n;i++){

for(j=1;j<=n;j++){

c=getchar();

map[i][j]=c-'0';

}

getchar();

}

scanf("%d%d%d%d",&begin_i,&begin_j,&end_i,&end_j);

printf("%d",BFS(begin_i,begin_j,end_i,end_j));

system("pause");

return 0;

}

int BFS(int begin_i,int begin_j,int end_i,int end_j)

{

int i;

map[begin_i][begin_j]=1;

Push(begin_i,begin_j,0);

while(rear!=front){

struct point t=Pop();

//printf("%d\n",t.distance);

int ti,tj;

if(t.x==end_i&&t.y==end_j)

return t.distance;

for(i=0;i<4;i++){

ti=t.x+xx[i];

tj=t.y+yy[i];

if(ti>0&&ti<=n&&tj>0&&tj<=n&&!map[ti][tj]){

map[ti][tj]=1;

Push(ti,tj,t.distance+1);

if(ti==end_i&&tj==end_j)

return t.distance+1;

}

}

}

}

void Push(int x,int y,int distance)

{

p[rear].x=x;

p[rear].y=y;

p[rear++].distance=distance;

}

struct point Pop()

{

struct point t=p[front++];

return t;

}

查看更多回复
提交回复