#include <iostream>
#include <queue>
#include <fstream>
using namespace std;

int a[21][21];
int w,h;
int dn;     //destiny num

struct point{
	int x,y;
	point(){}
	point(int a,int b){
		x=a;y=b;
	}
};
point cur;

queue<point> q;

int mark[21][21];
int step;     //标记走过的距离

int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};

bool isbond(int x,int y){
	if(x>=0&&x<h&&y>=0&&y<w&&a[x][y]!=2&&mark[x][y]==0)return true; 
	return false;
}


bool bfs(){
	int i,j,k;
	int sx=q.front().x;int sy=q.front().y;
	int dd=mark[sx][sy];
	for(i=0;i<4;i++){
		int curx=sx+dx[i];
		int cury=sy+dy[i];
		if(isbond(curx,cury)){
			if(a[curx][cury]==1){
				cur.x=curx;cur.y=cury;
				a[curx][cury]=0;
				mark[curx][cury]=dd+1;
				return true;
			}else{
				mark[curx][cury]=dd+1;
				point tmp(curx,cury);
				q.push(tmp);
			}
		}
	}
	q.pop();
	return false;
}





void main(){
//	ifstream cin("data.txt");
	while(1){
		cin>>w>>h;
		if(w==0)break;
		memset(a,0,sizeof(a));
		dn=0;
		int i,j;
		for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				char c;
				cin>>c;
				if(c=='x')a[i][j]=2;  //2代表有障碍物
				else if(c=='*'){     //*代表是目的地
					dn++;
					a[i][j]=1;
				}else if(c=='o'){ //出发地
					cur.x=i;cur.y=j;
				}
			}
		}
	/*	for(i=0;i<h;i++){
			for(j=0;j<w;j++){
				cout<<a[i][j]<<" ";
			}
			cout<<endl;
		}
	//	cout<<dn<<endl;*/
		
		int vn=0; //visitnum
		bool canfind=true;

		int ttstep=0;
		while(vn!=dn&&canfind){
			for(i=0;i<=h;i++)
				for(j=0;j<=w;j++)
					mark[i][j]=0;

			while(!q.empty())q.pop();
			q.push(cur);
			mark[cur.x][cur.y]=1;
			bool findp=false;
		//	step=0;
			while(!findp&&q.size()){
		//		step++;
				for(i=1;i<=q.size();i++){
					if(bfs()){
						findp=true;
						break;
					}
				}	
			}
			if(!findp){
				canfind=false;
			}else{
				ttstep+=mark[cur.x][cur.y]-1;
/*				cout<<endl;
				cout<<mark[cur.x][cur.y]-1<<endl;
				for(i=0;i<h;i++){
					for(j=0;j<w;j++){
						cout<<mark[i][j]<<" ";
					}
				cout<<endl;
				}*/
				vn++;
			}
		}
		if(!canfind)cout<<-1<<endl;
		else cout<<ttstep<<endl;

	}
}

• Re:我哪里错了？？为什么WA？？ 帮忙给看看： 谢谢！！！！ (42) 00648309 2008-05-04 14:45:37