題意：題目背景就是小時候玩的坦克大戰，求從起點到終點最少需要多少步。已知S和R是不能走得，E是空的，可以走，B是磚，只有打掉後才可以通過。
思路：很容易看出來這是一道廣搜的題目，但是因為走E和走B所需要的時間不一樣，因此不能用普通的隊列存點。因為對於走B來說，要先打掉磚才能通過，所以我們可以理解為走B需要兩步，而走E是指需要1步的。因此，不能用普通隊列來存。我們可以用STL中的優先隊列來存，每次從隊頭取出的都是步數少的點就可以了。這樣最先搜到的就是最優解。
代碼：
[cpp]
#include <iostream>
#include <cstdio>
#include <queue>
#include <string.h>
#include <algorithm>
#include <string>
using namespace std;
#define CLR(arr,val) memset(arr,val,sizeof(arr))
struct point{
int x,y,step;
bool operator < (const point & p) const{
return step > p.step;
}
};
const int N = 305;
char map[N][N];
int sx,sy,ex,ey,flag[N][N],row,col;
int addx[4] = {0,0,1,-1};
int addy[4] = {1,-1,0,0};
int bfs(){
priority_queue<point> qq;
point p;
p.x = sx; p.y = sy; p.step = 0;
flag[sx][sy] = 1;
qq.push(p);
while(!qq.empty()){
point topp = qq.top();
qq.pop();
if(topp.x == ex && topp.y == ey){
return topp.step;
}
else{
for(int i = 0; i < 4; ++i){
int newx = topp.x + addx[i];
int newy = topp.y + addy[i];
if(newx >= 0 && newx < row && newy >= 0 && newy < col && !flag[newx][newy] ){
if(map[newx][newy] == 'S' || map[newx][newy] == 'R')
continue;
point newp;
newp.x = newx;
newp.y = newy;
flag[newx][newy] = 1;
if(map[newx][newy] == 'B'){
newp.step = topp.step + 2;
}
else
newp.step = topp.step + 1;
qq.push(newp);
}
}
}
}
return -1;
}
int main(){
//freopen("1.txt","r",stdin);
while(scanf("%d%d",&row,&col) != EOF){
if(row + col == 0)
break;
CLR(flag,0);
CLR(map,'0');
for(int i = 0; i < row; ++i){
for(int j = 0; j < col; ++j){
cin >> map[i][j];
if(map[i][j] == 'Y'){
sx = i;
sy = j;
}
else if(map[i][j] == 'T'){
ex = i;
ey = j;
}
} www.2cto.com
}
int ans = bfs();
printf("%d\n",ans);
}
return 0;
}
作者：wmn_wmn
