BFS。找到終點之后可以立即跳出循環，提高效率，但是因為數據規模不大，我沒有這么做，見諒~~
以下是我的代碼：
#include<iostream>
#define maxn 1001
#define INF 20000007
using namespace std;
const long xd[]={-1,1,0,0},yd[]={0,0,1,-1};
typedef struct
{
long counter,front,rear,x[maxn*maxn],y[maxn*maxn];
}queue;
void Clear(queue &q)
{
q.counter=0;q.front=0;q.rear=-1;
}
bool Empty(queue &q)
{
return (q.counter==0);
}
void Push(queue &q,long rx,long ry)
{
q.counter++;q.rear++;
q.x[q.rear]=rx;q.y[q.rear]=ry;
}
void Pop(queue &q,long &rx,long &ry)
{
q.counter--;rx=q.x[q.front];ry=q.y[q.front];
q.front++;
}
long n,bx,by,ex,ey,d[maxn][maxn];
bool g[maxn][maxn];
queue q;
int main()
{
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
cin>>n;
for(long i=1;i<=n;i++)
{
for(long j=1;j<=n;j++)
{
char r;
cin>>r;
g[i][j]=(r=='0'?false:true);
d[i][j]=INF;
}
getchar();
}
cin>>bx>>by;
cin>>ex>>ey;
// Input
Clear(q);
d[bx][by]=0;
Push(q,bx,by);
while(!Empty(q))
{
long xx,yy;Pop(q,xx,yy);
for(long k=0;k<4;k++)
{
long rx=xx+xd[k],ry=yy+yd[k];
if(rx>=1&&rx<=n&&ry>=1&&ry<=n&&!g[rx][ry]&&d[rx][ry]>=INF)
{
d[rx][ry]=d[xx][yy]+1;
Push(q,rx,ry);
}
}
}
cout<<d[ex][ey]<<endl;
return 0;
}
posted on 2010-10-15 22:43
lee1r 閱讀(361)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：搜索