|
题意：题目背景就是小时候玩的坦克大战，求从起点到终点最少需要多少步。已知S和R是不能走得，E是空的，可以走，B是砖，只有打掉后才可以通过。
思路：很容易看出来这是一道广搜的题目，但是因为走E和走B所需要的时间不一样，因此不能用普通的队列存点。因为对于走B来说，要先打掉砖才能通过，所以我们可以理解为走B需要两步，而走E是指需要1步的。因此，不能用普通队列来存。我们可以用STL中的优先队列来存，每次从队头取出的都是步数少的点就可以了。这样最先搜到的就是最优解。
代码：
[cpp]
#include
#include
#include
#include
#include
#include
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 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
|