南阳理工OJ 284 坦克大战 宽度优先遍历

/*
比较简单的一道题，只要细心，思路清楚，基本都可以一遍过的
先把在地图上的实物数量化，墙是2，路是1，出界、河、铁墙都是-1
表示不能走。
然后用宽度遍历，起始点为队头，每次遍历上下左右四个方向
如果地图为-1，就不操作
如过地图不为-1，但没有遍历过，那么这块地图的步数应该是
队头地图的步数加上这块地图需要的步数。
如过地图不为-1，遍历过，那么这块地图的步数应该是
队头地图的步数加上这块地图需要的步数，和原来这块地图的
步数相比，最小的步数。
*/
#include<iostream>
#include<string.h>
using namespace std;
int n,m;
int map[300+10][300+10];
int result[300+10][300+10];
int queue[100000];
int base,top;
int fang[4][2]={0,1,0,-1,1,0,-1,0};
int main()
{
//	freopen("in.txt","r",stdin);
	int i,j,x,y,x1,y1,resx,resy;
	char c;
	while(cin>>n>>m,n)
	{
		top=base=0;
		memset(map,-1,sizeof(map));
		memset(result,-1,sizeof(result));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				cin>>c;
				if(c=='Y')
				{
					map[i][j]=0;
					result[i][j]=0;
					queue[top++]=i*1000+j;//起始坐标入队
				}
				else if(c=='B')map[i][j]=2;
				else if(c=='E')map[i][j]=1;
				else if(c=='T')resx=i,resy=j,map[i][j]=1;//标记要求的坐标
			}
		while(base!=top)
		{
			for(i=0;i<4;i++)
			{
				x=queue[base]/1000;
				x1=x+fang[i][0];
				y=queue[base]%1000;
				y1=y+fang[i][1];//算出横纵坐标
				if(map[x1][y1]==-1)continue;//如果在地图上走不成就继续
				if(result[x1][y1]==-1||(result[x1][y1]>result[x][y]+map[x1][y1]))
				{//如果没有走过或者走过但不是最优，就更新为最优，继续入队
					result[x1][y1]=result[x][y]+map[x1][y1];
					queue[top++]=x1*1000+y1;
				}
			}
			base++;//判断完一个出队一个
		}
		if(result[resx][resy]==-1)cout<<"-1\n";
		else cout<<result[resx][resy]<<endl;
	}
	return(0);
}

 

/*
也可以用优先队列来做，速度应该会快一点；
每次找最短的路走，走一个，就把这一个路
标记一下，下一次就不用走这条路.
其他的和上一个方法差不多
*/
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
char map[300+2][300+2];
char fang[4][2]={0,1,0,-1,1,0,-1,0};
struct node
{
	short x,y;
	int date;
}a,b;
bool operator<(const node &a,const node &b)//重载运算符
{
	return(a.date>b.date);
}
priority_queue<node>q;
int n,m;
int main()
{
//	freopen("in.txt","r",stdin);
	int i,j,x,y,f;
	char c;
	while(cin>>n>>m,n)
	{
		memset(map,-1,sizeof(map));
		for(i=1;i<=n;i++)
			for(j=1;j<=m;j++)
			{
				cin>>c;
				if(c=='Y')
				{
					map[i][j]=-1;
					a.x=i;a.y=j;a.date=0;q.push(a);
				}
				else if(c=='B')map[i][j]=2;
				else if(c=='E')map[i][j]=1;
				else if(c=='T')map[i][j]=1,x=i,y=j;
			}
		while(!q.empty())
		{
			a=q.top();
			q.pop();
			f=0;
			for(i=0;i<4;i++)
			{
				b.x=a.x+fang[i][0];
				b.y=a.y+fang[i][1];
				if(map[b.x][b.y]==-1)continue;
				b.date=a.date+map[b.x][b.y];
				map[b.x][b.y]=-1;//标记为不能走
				if(b.x==x&&b.y==y){f=1;break;}//找到就退出
				q.push(b);
			}
			if(f)break;
		}
		if(f)cout<<b.date<<endl;//输出
		else cout<<"-1\n";
		while(!q.empty())q.pop();//清空队列
	}
	return(0);
}