ZOJ1649/HDU1242 간단한 BFS + 작은 변형

이 문제의 대체적인 의미는 하나의 미궁 안에서 구원천사, r는 천사의 친구 a는 천사, x는 위병을 대표한다.
위병을 만나면 그를 때려죽이는 데는 각 부서의 시간이 얼마나 걸려야 천사가 있는 위치에 도착할 수 있느냐고 물었다.
이 문제를 보자마자 첫 번째 반응은 코드만 검색하고 금방 다 썼어요. 테스트 샘플이 통과해서 바로 제 멍청한 눈으로 제출했어요.
Wa, 계속 Wa 고민 죽겠어!나는 사악한 것을 믿지 않고 다른 사람의 코드를 찾아갔는데, 첫눈에 본 것은 우선 대기열이었다.
나는 일반 대열을 사용하면 한 걸음 한 걸음 밖으로 수색할 수 있고 멈출 수 없다는 것을 문득 깨달았다. 이것은 일반 대열의 장점이자 단점이다.
결과적으로 나는 우선 대기열을 사용한 후 내 코드의 기초 위에서 조금만 바꾸면 우선 대기열의 기능을 실현할 수 있다.
우선 대기열은 순서대로 작은 것부터 큰 것까지 시간을 배열하기 때문에 약간의 수정으로 과감하게 0ms를 통과하여 정말 기쁩니다!

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<limits.h>
  5 #include<cstdlib>
  6 #include<queue>
  7 
  8 using namespace std;
  9 
 10 typedef struct 
 11 {
 12   int x, y;
 13   int step;
 14 }Point;
 15 
 16 priority_queue<Point> q;
 17 bool operator<(Point a, Point b)
 18 {
 19     return a.step > b.step;
 20 }
 21 
 22 char map[201][201];
 23 int visit[201][201];
 24 int N, M, ok, num, si, sj;
 25 int dx[4] = {1,-1,0,0};
 26 int dy[4] = {0,0,1,-1}; 
 27    
 28 int True(Point V)
 29 { 
 30    if(V.x>=0 && V.x<N && V.y>=0 && V.y<M)
 31      return 1;
 32    return 0;
 33 }
 34   
 35 int main()
 36 {
 37        int i, j, ax, ay;
 38        Point Start, end;
 39        
 40      while(scanf("%d%d", &N, &M) != EOF)
 41      {
 42         getchar();                 
 43        for(i=0; i<N; i++)
 44        {
 45           scanf("%s",map[i]);
 46           getchar();
 47        }      
 48        for(i=0; i<N; i++)
 49          for(j=0; j<M; j++)
 50          { 
 51            if(map[i][j] == 'r')
 52            { 
 53               si = i;
 54               sj = j;  
 55            }
 56            if(map[i][j] == 'a')
 57            {
 58              ax = i;
 59              ay = j;
 60            }
 61          }
 62         memset(visit, 0, sizeof(visit));
 63         Start.x = si;
 64         Start.y = sj;
 65         Start.step = 0;
 66         ok = 0;
 67         visit[Start.x][Start.y] = 1;
 68         q.push(Start);
 69         while( !q.empty() )
 70         {
 71            Point u = q.top();
 72            q.pop();
 73            if(u.x==ax&&u.y==ay)
 74            {
 75               ok = 1;
 76               printf("%d
",u.step);
 77               break;
 78            }      
 79            for(i=0; i<4; i++)
 80            {
 81               Point v;
 82               v.x = u.x + dx[i];
 83               v.y = u.y + dy[i];
 84               if(True(v)&&!visit[v.x][v.y]&&map[v.x][v.y]!='#')
 85               {
 86                  if(map[v.x][v.y]=='x')
 87                    v.step = u.step + 2;
 88                  else
 89                    v.step = u.step + 1;                                               
 90                   visit[v.x][v.y] = 1;
 91                   q.push(v);
 92               }
 93            }  
 94         }           
 95         if(!ok)  
 96           printf("Poor ANGEL has to stay in the prison all his life.
");
 97         while( !q.empty() )
 98         {
 99           q.pop();
100         }
101      }        
102      return 0;
103 }