http://poj.org/problem?id=2312
Battle City
| Time Limit: 1000MS | Memory Limit: 65536K |
| Total Submissions: 5986 | Accepted: 1971 |
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.
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).
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
8
Source
POJ Monthly,鲁小石
这题是要求从'Y'到'T'的最小步数最直接的想法必然是bfs但是这题有个变化就是碰到'B'的时候你要先停留一秒（这一秒是用来发射炮弹的），然后才可以继续走。其实说白了就是碰到'B'你要走两步。而bfs都是走一步的。
这样的话不能使用一般的BFS广搜来做。本题可以使用改进过的广搜。有些节点需要耗费2个单位时间，要想用BFS就得改一下，由于BFS每次只能操作一步，要不就是扩展，要不就是破坏砖墙。所以只需检查该点是不是'B'，是的话就得停一步，不是的话，继续扩展，也就是说某些点的扩展慢了一拍，所以从队列里出来的点就判断一下再看执行哪个操作。
- 这道题中B点需要操作两步，所以遇到B点后不能+2后直接压进队列，需要在原地停一下，不能扩展到其他点，相当于他只能扩展到自身，所以就把自身压进队列里map[x][y]='E'是因为破坏砖墙一次就够了，不然下次，还是'B'，不断压进队列，不断在原地停留
- 平常一般是考虑“入队列” 的点，这次要考虑“出队列” 的点是否满足条件！
解题思路：
是一个变形的BFS，与普通的BFS相比，它不需要做访问标记，访问过的点还可以二次访问，只是在二次访问的时候，要判断第二次访问时的时间是不是比第一次的时间短，若短，则更新时间值，并继续访问，反之，则不访问；这里就是解题的关键理解了这里一切就好说了。。。。
这里还有一种感觉 和自己的想法很像。。。
http://blog.csdn.net/hackbuteer1/article/details/6719983
#include<iostream>
#include<queue>
using namespace std;
#define N 303
struct node
{
int x,y;
}p1,p2;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//搜索的四个方向
int sx,sy,ex,ey;//起点和终点
char map[N][N];
int mark[N][N];//记录步数
int n,m,flag;
void BFS()
{
queue<node>q;
int now_tures;
p1.x=sx;
p1.y=sy;
q.push(p1);//如队列
mark[sx][sy]=0;//开始步数为0
while(!q.empty())//队列非空
{
p1=q.front();//取出对头元素
q.pop();//删除对头元素
if(p1.x==ex&&p1.y==ey)
{
flag=true;
return;
}
for(int i=0;i<4;i++)//四个方向搜索
{
p2.x=p1.x+dir[i][0];//下一个点的坐标
p2.y=p1.y+dir[i][1];
if(p2.x<0||p2.x>=m||p2.y<0||p2.y>=n||map[p2.x][p2.y]=='S'||map[p2.x][p2.y]=='R') //边界||是否可走
continue;
if(map[p2.x][p2.y]=='B')//碰到'B'的话步数+2
now_tures=mark[p1.x][p1.y]+2;
else//'E'步数+1
now_tures=mark[p1.x][p1.y]+1;
if(mark[p2.x][p2.y]>now_tures)//最关键的地方
{
//访问过的点还可以二次访问，只是在二次访问的时候，
//要判断第二次访问时的时间是不是比第一次的时间短，若短，则更新时间值，并继续访问，
//反之，则不访问；
mark[p2.x][p2.y]=now_tures;//如果以(p2.x,p2.y)为终点的最小路径长度小于该次的路径长度
q.push(p2);//这时候才进队列
}
}
}
}
int main()
{
int i,j;
while(scanf("%d%d",&m,&n))
{
getchar();
if(m==0&&n==0)
break;
for(i=0;i<m;i++)//初始化为无穷大
for(j=0;j<n;j++)
mark[i][j]=INT_MAX;
for(i=0;i<m;i++)
for(j=0;j<n;j++)
{
cin>>map[i][j];
if(map[i][j]=='Y')//记录起点的坐标
{
sx=i;
sy=j;
}
else if(map[i][j]=='T')//记录终点的坐标
{
ex=i;
ey=j;
}
}
flag=0;
BFS();
if(flag)
printf("%d\n",mark[ex][ey]);
else
printf("-1\n");
}
return 0;
}