1972: 坦克大战 bfs+优先队列

Battle City

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 10594		Accepted: 3534

Description

Many of us had played the game "Battle city" in our childhood, and some people (like me) even often play it on computer now.

1972: 坦克大战 bfs+优先队列

What we are discussing is a simple edition of this game. Given a map that consists of empty spaces, rivers, steel walls and brick walls only. Your task is to get a bonus as soon as possible suppose that no enemies will disturb you (See the following picture).

1972: 坦克大战 bfs+优先队列

Your tank can't move through rivers or walls, but it can destroy brick walls by shooting. A brick wall will be turned into empty spaces when you hit it, however, if your shot hit a steel wall, there will be no damage to the wall. In each of your turns, you can choose to move to a neighboring (4 directions, not 8) empty space, or shoot in one of the four directions without a move. The shot will go ahead in that direction, until it go out of the map or hit a wall. If the shot hits a brick wall, the wall will disappear (i.e., in this turn). Well, given the description of a map, the positions of your tank and the target, how many turns will you take at least to arrive there?

Input

The input consists of several test cases. The first line of each test case contains two integers M and N (2 <= M, N <= 300). Each of the following M lines contains N uppercase letters, each of which is one of 'Y' (you), 'T' (target), 'S' (steel wall), 'B' (brick wall), 'R' (river) and 'E' (empty space). Both 'Y' and 'T' appear only once. A test case of M = N = 0 indicates the end of input, and should not be processed.

Output

For each test case, please output the turns you take at least in a separate line. If you can't arrive at the target, output "-1" instead.

Sample Input

3 4
YBEB
EERE
SSTE
0 0

Sample Output

Source

这题不算难，Y表示起点，T表示终点，R表示河流，不能通过，S表示钢筋，不能通过，E能通过，耗时1，B也能通过，耗时2.

找出到达终点的最小耗时，输出，如果不能达到，输出-1.一度让我以为是dfs，后来发现是最小，改为bfs，用队列，wa了n次。

后来，搜了搜题解，看到有人用优先队列，用优先队列保证了最小耗时，因为每一次弹出队列的都是到达这个坐标耗时最小的。

说说我错的地方。

	bool operator < (const  node &a)const    //  优先队列 重载小于号 
	{
		return t>a.t;
	}

这个地方我少了return，优先队列默认识从大到小排列的，少了个return 每次弹出都是最大的，让我找了半天的bug

看来stl还得多熟悉。

还有另外一种重载<的方法

#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
using namespace std;
int n,m,sx,sy,ex,ey;
#define range 305
char map[range][range];
bool vis[range][range];
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
int sum=100000;
int cnt=0;
int f=0;
struct node{
	int x,y;
	int t;              // t 表示达到该点所需要的时间。 
	friend bool operator < (const  node &a,const node &b)   //  优先队列 重载小于号 
	{
		return a.t>b.t;
	}
};

int bfs(int a,int b)
{
   priority_queue<node> q;
   node te;
   te.x=sx;
   te.y=sy;
   te.t=0;
   q.push(te);
    while(!q.empty())
    {
    	
    	node tem=q.top();
    
    	q.pop();
    	for(int i=0;i<4;i++)
		{
			int tx=tem.x+dir[i][0];
			int ty=tem.y+dir[i][1];
			if(tx>=0&&ty>=0&&tx<=n-1&&ty<=m-1&&vis[tx][ty]==false)
			{
			    if(map[tx][ty]!='S'&&map[tx][ty]!='R')
			    {
			    	
			    	node temp;
					temp.x=tx;
					temp.y=ty;
					temp.t=tem.t;
					vis[tx][ty]=true;
					if(map[tx][ty]=='B')
					temp.t+=2;
					else
					temp.t+=1;
					if(map[tx][ty]=='T')
					{
						f=1;
						
						if(temp.t<sum)
						sum=temp.t;
						
					}
					q.push(temp);
				}
			}
		}
    }
}
int main()
{
	while(~scanf("%d %d",&n,&m))
	{
		if(n==0&&m==0)
		break;
		memset(vis,false,sizeof(vis));    // 初始化 很重要 
		memset(map,0,sizeof(map));
		int i,j;
		
		for(i=0;i<n;i++)
		scanf("%s",map[i]);
		for(i=0;i<n;i++)
		for(j=0;j<m;j++)
		{
			
			if(map[i][j]=='Y')
			{
				sx=i;
				sy=j;
			}
		}
		vis[sx][sy]=true;
		bfs(sx,sy);
		if(f)
		cout<<sum<<endl;
		else
		cout<<-1<<endl;
		f=0;
		cnt=0;
		sum=10000;
	}
	return 0;
}

1972: 坦克大战 bfs+优先队列

相关推荐