POJ 2312 Battle City 优先多列+bfs

 
题意：题目背景就是小时候玩的坦克大战，求从起点到终点最少需要多少步。已知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