| ||||||||||
| 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 | |||||||||
我用纯bfs做的 但为什么总wa???希望大牛看看。谢谢#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct node{
int x;
int y;
int step;
}d[250*250];
char map[21][21];
bool used[21][21];
int n,m;
int tot;
int cnt;
int ans=0;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void bfs()
{
queue <node> q;
int i,j;
memset(used,0,sizeof(used));
q.push(d[cnt-1]);
used[d[cnt-1].x][d[cnt-1].y]=true;
while(!q.empty())
{
node fromv=q.front();
q.pop();
for(i=0;i<4;i++)
{
node t;
t.x=fromv.x+dir[i][0];
t.y=fromv.y+dir[i][1];
t.step=fromv.step+1;
if(t.x>=0 && t.x<n && t.y>=0 && t.y<m &&
!used[t.x][t.y] && map[t.x][t.y]!='x')
{
if(map[t.x][t.y]=='*')
{
tot--;
ans+=t.step;
map[t.x][t.y]='.';
d[cnt].x=t.x;
d[cnt].y=t.y;
d[cnt++].step=0;
return;
}
used[t.x][t.y]=true;
q.push(t);
}
}
}
}
int main()
{
while(cin>>m>>n && (m+n))
{
int i,j;
cin.ignore();
tot=0;
cnt=0;
ans=0;
for(i=0;i<n;i++)
{
cin.getline(map[i],25);
for(j=0;j<m;j++)
{
if(map[i][j]=='*')
tot++;
else if(map[i][j]=='o')
{
d[cnt].x=i;
d[cnt].y=j;
d[cnt++].step=0;
}
}
}
int num=tot;
if(!tot)
cout<<0<<endl;
else
{
for(i=0;i<num;i++)
bfs();
if(tot)
cout<<"-1"<<endl;
else
cout<<ans<<endl;
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator