題目大意：在N×M的方格上有些地方不可到達，有些地方有警衛，打敗警衛需要額外1個單位的時間。給出起點和終點，求出最少需要多少時間。
由于每一步消耗的時間可能不一樣，不能夠直接BFS，因此采用SPFA。
以下是我的代碼：
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int kMaxn(207);
const int kInf(0x7f7f7f7f);
const int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
struct Point
{
Point(int valuex,int valuey):x(valuex),y(valuey) {}
int x,y;
};
int n,m,x,y,endx,endy,d[kMaxn][kMaxn];
char g[kMaxn][kMaxn];
bool inq[kMaxn][kMaxn];
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;i++)
{
getchar();
for(int j=1;j<=m;j++)
{
scanf("%c",&g[i][j]);
if(g[i][j]=='r')
{
x=i;
y=j;
}
else if(g[i][j]=='a')
{
endx=i;
endy=j;
}
}
}
queue<Point> q;
memset(inq,false,kMaxn*kMaxn*sizeof(bool));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
d[i][j]=kInf;
d[x][y]=0;
q.push(Point(x,y));
inq[x][y]=true;
while(!q.empty())
{
Point now=q.front();
q.pop();
inq[now.x][now.y]=false;
for(int i=0;i<4;i++)
{
int newx(now.x+dx[i]),newy(now.y+dy[i]);
if(newx<1 || newx>n || newy<1 || newy>m || g[newx][newy]=='#')
continue;
int w(g[newx][newy]=='x'?2:1);
if(d[newx][newy]>d[now.x][now.y]+w)
{
d[newx][newy]=d[now.x][now.y]+w;
if(!inq[newx][newy])
{
q.push(Point(newx,newy));
inq[newx][newy]=true;
}
}
}
}
if(d[endx][endy]<kInf)
printf("%d\n",d[endx][endy]);
else
printf("Poor ANGEL has to stay in the prison all his life.\n");
}
return 0;
}
posted on 2011-05-26 16:09
lee1r 閱讀(273)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論