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