BFS HDOJ 1242 Rescue-白红宇

BFS HDOJ 1242 Rescue

阅读量：5127 次

发布时间：2019-06-13

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

题意：从r走到a，遇到x多走一步，问最小走到a的步数

分析：因为r有多个，反过来想从a走到某个r的最小步数，简单的BFS。我对这题有特殊的感情，去年刚来集训队时肉鸽推荐了这题，当时什么都不会，看个数组模拟队列的BFS看的头晕，现在看起来也不过如此，额，当年开始是从r走到a的，因为数据巨弱才过的，应该要用到优先队列。

/************************************************* Author        :Running_Time* Created Time  :2015/9/25 星期五 09:13:51* File Name     :B_BFS.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 2e2 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;const double EPS = 1e-8;struct Angle { int x, y, step; Angle () {} Angle (int x, int y, int step) : x (x), y (y), step (step) {}};int dx[4] = {-1, 1, 0, 0};int dy[4] = {0, 0, -1, 1};bool vis[N][N];char maze[N][N];int n, m;bool judge(int x, int y) { if (x < 1 || x > n || y < 1 || y > m || vis[x][y] || maze[x][y] == '#') return false; else return true;}void BFS(Angle s) { int ret = INF; memset (vis, false, sizeof (vis)); queue
                      
                        Q; Q.push (s); vis[s.x][s.y] = true; while (!Q.empty ()) { Angle r = Q.front (); Q.pop (); for (int i=0; i<4; ++i) { int tx = r.x + dx[i]; int ty = r.y + dy[i]; if (!judge (tx, ty)) continue; vis[tx][ty] = true; if (maze[tx][ty] == 'r') { ret = min (ret, r.step + 1); continue; } else if (maze[tx][ty] == 'x') { Q.push (Angle (tx, ty, r.step + 2)); continue; } else Q.push (Angle (tx, ty, r.step + 1)); } } if (ret == INF) puts ("Poor ANGEL has to stay in the prison all his life."); else printf ("%d\n", ret);}int main(void) { while (scanf ("%d%d", &n, &m) == 2) { for (int i=1; i<=n; ++i) { scanf ("%s", maze[i] + 1); } bool find = false; Angle start; for (int i=1; i<=n && !find; ++i) { for (int j=1; j<=m; ++j) { if (maze[i][j] == 'a') { start = Angle (i, j, 0); find = true; break; } } } BFS (start); } return 0;}

当年的代码不忍直视。。。

#include
     
      typedef struct point{    int x,y,step;}target;int N,M,dir[4][2]={0,1,0,-1,1,0,-1,0},ax,ay;int flag[202][202];char map[302][302];target que[40005];int BFS(target start){    int end,top,i;    int min=1000000;    target in,next;    end=top=0;    que[top]=start;    while (top>=end)    {        in=que[end];        end=(end+1);        for (i=0;i<4;i++)        {            next.x=in.x+dir[i][0];            next.y=in.y+dir[i][1];            if (map[next.x][next.y]=='r')            {                if (min>in.step+1)                    min=in.step+1;            }            if (next.x>=0&&next.x
      
       =0&&next.y
       
        in.step+1)                {                    next.step=in.step+1;                    if (map[next.x][next.y]=='x')                        next.step++;                    flag[next.x][next.y]=next.step;                    top=(top+1);                    que[top]=next;                }            }        }    }    if (min!=1000000)return min;    else        return -1;}int main(){    int i,j,num;    target start;    while (scanf("%d%d",&N,&M)!=EOF)    {        for (i=0;i

转载于:https://www.cnblogs.com/Running-Time/p/4837255.html

你可能感兴趣的文章