Easy BFS。
Here is my code:
#include<iostream>
#define maxn 107
using namespace std;
const long xd[]={-1,-1,0,1,1,1,0,-1},yd[]={0,-1,-1,-1,0,1,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++;
if(q.rear>=maxn*maxn) q.rear=0;
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++;
if(q.front>=maxn*maxn) q.front=0;
}
long n,m,mx,my,ans,g[maxn][maxn],d[maxn][maxn];
queue q;
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
cin>>n>>m>>mx>>my;
for(long i=1;i<=m;i++)
{
char ch;
for(long j=1;j<=n;j++)
{
cin>>ch;
if(ch=='.') g[i][j]=1;
else g[i][j]=0;
}
}
long t=my;my=mx;mx=m-t+1;
// Input
/*
for(long i=1;i<=m;i++)
{
for(long j=1;j<=n;j++)
cout<<g[i][j];
cout<<endl;
}
cout<<endl<<mx<<" "<<my<<endl<<endl;
//*/
Clear(q);Push(q,mx,my);
d[mx][my]=0;g[mx][my]=0;
while(!Empty(q))
{
long xx,yy,nx,ny;Pop(q,xx,yy);
for(long k=0;k<8;k++)
{
nx=xx+xd[k];
ny=yy+yd[k];
if(nx>=1&&nx<=m&&ny>=1&&ny<=n&&g[nx][ny])
{
Push(q,nx,ny);
d[nx][ny]=d[xx][yy]+1;g[nx][ny]=0;
}
}
}
ans=0;
for(long i=1;i<=m;i++)
for(long j=1;j<=n;j++)
if(ans<d[i][j])
ans=d[i][j];
cout<<ans<<endl;
return 0;
}
posted on 2010-10-22 11:29
lee1r 閱讀(649)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
題目分類(lèi)：搜索