HDU 1242 Rescue-白红宇

HDU 1242 Rescue

阅读量：5876 次

发布时间：2019-06-19

本文共 3033 字，大约阅读时间需要 10 分钟。

bfs问题。

Angel有被关在监狱，她有非常多朋友要去救她。

#表示墙，.表示路，x表示警卫，r表示她的朋友。

因为可能有非常多朋友，可是Angel仅仅有一个，所以搜索起点设为Angel。仅仅要找到一个朋友表示能走出去。

走一格须要1，杀死警卫须要1，假设使用 queue 不能直接加2.

由于会出现这样的情况

4 8axxxxxxr........................

假设直接加2的话，答案就不是9.

可是使用 priority_queue 就能够无视这样的情况了。我也要開始习惯使用priority_queue。

queue版本号。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define INF 0x7fffffff#define eps 1e-8#define LL long long#define PI 3.141592654#define CLR(a,b) memset(a,b,sizeof(a))#define FOR(i,a,n) for(int i= a;i< n ;i++)#define debug puts("==fuck==")#define acfun std::ios::sync_with_stdio(false)#define SIZE 1000+10using namespace std;int xx[]={0,0,-1,1};int yy[]={-1,1,0,0};int n,m;char g[201][201];struct lx{ int x,y,lv; void init(int xx,int yy,int llv) { x=xx,y=yy,lv=llv; }};lx start,thend;void bfs(){ queue
                 
                  q; bool vis[201][201]; CLR(vis,0); q.push(start); vis[start.x][start.y]=1; while(!q.empty()) { lx tmp=q.front(); q.pop();// printf("%d %d == %d\n",tmp.x,tmp.y,tmp.lv);// system("pause"); if(g[tmp.x][tmp.y]=='r') { printf("%d\n",tmp.lv); return ; } FOR(k,0,4) { int x=tmp.x+xx[k]; int y=tmp.y+yy[k]; if(x<0||y<0||x>=n||y>=m||g[x][y]=='#'||vis[x][y]) continue; lx now; if(g[x][y]=='x') { now.init(tmp.x,tmp.y,tmp.lv+1); g[x][y]='.'; } else { now.init(x,y,tmp.lv+1); vis[x][y]=1; } q.push(now); } } puts("Poor ANGEL has to stay in the prison all his life.");}int main(){ while(~scanf("%d%d",&n,&m)) { char str[201]; FOR(i,0,n) { scanf("%s",str); FOR(j,0,m) { g[i][j]=str[j]; if(g[i][j]=='a') start.init(i,j,0); } } bfs(); }}

priority_queue 版本号

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define INF 0x7fffffff#define eps 1e-8#define LL long long#define PI 3.141592654#define CLR(a,b) memset(a,b,sizeof(a))#define FOR(i,a,n) for(int i= a;i< n ;i++)#define debug puts("==fuck==")#define acfun std::ios::sync_with_stdio(false)#define SIZE 200+10using namespace std;int xx[]={0,0,-1,1};int yy[]={-1,1,0,0};int n,m;char g[SIZE][SIZE];struct lx{ int x,y,lv; void init(int xx,int yy,int llv) { x=xx,y=yy,lv=llv; } friend bool operator< (lx a,lx b) { return a.lv>b.lv; }};lx start;void bfs(){ priority_queue
                 
                  q; bool vis[SIZE][SIZE]; CLR(vis,0); vis[start.x][start.y]=1; q.push(start); while(!q.empty()) { lx tmp=q.top(); q.pop(); if(g[tmp.x][tmp.y]=='r') { printf("%d\n",tmp.lv); return ; } FOR(k,0,4) { int x=tmp.x+xx[k]; int y=tmp.y+yy[k]; if(x<0||y<0||x>=n||y>=m||vis[x][y]||g[x][y]=='#') continue; lx now; if(g[x][y]=='x') now.init(x,y,tmp.lv+2); else now.init(x,y,tmp.lv+1); vis[x][y]=1; q.push(now); } } puts("Poor ANGEL has to stay in the prison all his life.");}int main(){ while(~scanf("%d%d",&n,&m)) { char str[SIZE]; FOR(i,0,n) { scanf("%s",str); FOR(j,0,m) { g[i][j]=str[j]; if(g[i][j]=='a') start.init(i,j,0); } } bfs(); }}