| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
求解释,我对得莫名其妙#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int m,n;
int a[305][305];
bool vis[305][305];
struct Cxy
{
int x,y;
bool operator==(struct Cxy tmp)
{
if(tmp.x==x && tmp.y==y)return true;
return false;
}
}My_loca,trea_loca;
struct BFS
{
struct Cxy loca;
int step;
}tmp,top;
priority_queue<BFS> Q;
int tex[4]={1,0,-1,0};
int tey[4]={0,1,0,-1};
bool operator<(const BFS &a,const BFS &b)
{
return a.step>b.step;//为甚麽是这样?
}
void init()
{
memset(vis,1,sizeof(vis));
char c;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
vis[j][i]=0;
cin>>c;
a[j][i]=1;
if(c=='Y'){My_loca.x=j;My_loca.y=i;}
else if(c=='T'){trea_loca.x=j;trea_loca.y=i;}
else if(c=='B')a[j][i]++;
else if(c=='S' || c=='R')a[j][i]=999999999;
}
}
}
bool ok(struct BFS tmp)
{
if(tmp.step>n*m*5)return false;
if(tmp.loca.x<1 || tmp.loca.x>m)return false;
if(tmp.loca.y<1 || tmp.loca.y>n)return false;
if(vis[tmp.loca.x][tmp.loca.y])return false;
return true;
}
int bfs()
{
tmp.step=0;tmp.loca=My_loca;
vis[My_loca.x][My_loca.y]=1;
Q.push(tmp);
while(!Q.empty())
{
top=Q.top();Q.pop();
if(top.loca==trea_loca)return top.step;
for(int i=0;i<4;i++)
{
tmp=top;
tmp.loca.x+=tex[i];tmp.loca.y+=tey[i];
tmp.step+=a[tmp.loca.x][tmp.loca.y];
if(!vis[tmp.loca.x][tmp.loca.y] && tmp.step<180005)
{
vis[tmp.loca.x][tmp.loca.y]=1;
Q.push(tmp);
}
}
}
return -1;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
if(n==0&&m==0)break;
init();
while(!Q.empty())Q.pop();
printf("%d\n",bfs());
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator