hdu 1242 Rescue BFS+优先队列

题目大意就是输入M,N。然后输入map，如果遇到.那么就可一走，耗时为一，如果不为‘x’就是遇到守卫，需要杀死，额外耗时一，'#'是墙。

代码：

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 struct node
  4 {
  5     int x,y;
  6     int step;
  7 }q[100000];
  8 char map[250][250];
  9 int vis[250][250];
 10 int to[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//方向
 11 int f,r,m,n,leap,flag;
 12 
 13 void sort()//优先队列的排序
 14 {
 15     int i;
 16     for(i = r;i > f;i--)
 17     {
 18         struct node temp;
 19         if(q[i].step < q[i-1].step)
 20         {
 21             temp = q[i];
 22             q[i] = q[i-1];
 23             q[i-1] = temp;
 24         }
 25         else
 26         break;
 27     }
 28 }
 29 void bfs(int px,int py)//bfs
 30 {
 31     memset(vis,0,sizeof(vis));
 32     int i;
 33     f = r = 0;
 34     q[r].x = px;
 35     q[r].y = py;
 36     q[r].step = 0;
 37     r++;
 38 
 39     while(f < r)
 40     {
 41         struct node now,temp;
 42         now = q[f++];
 43         for(i = 0;i < 4;i++)
 44         {
 45             temp.x = now.x + to[i][0];
 46             temp.y = now.y + to[i][1];
 47             temp.step = now.step+1;
 48             if(temp.x >= 0 && temp.x < m && temp.y >= 0 && temp.y < n)//查边界
 49             {
 50                 if(map[temp.x][temp.y] != '#' && !vis[temp.x][temp.y])
 51                 {
 52                     vis[temp.x][temp.y] = 1;
 53                     if(map[temp.x][temp.y] == '.')
 54                     {
 55                         q[r] = temp;
 56                         sort();
 57                     }
 58                     else if(map[temp.x][temp.y] == 'x')
 59                     {
 60                         temp.step++;
 61                         q[r] = temp;
 62                         sort();
 63                     }
 64                     else if(map[temp.x][temp.y] == 'r')
 65                     {
 66                         q[r] = temp;
 67                         sort();
 68                         leap = 1;
 69                         break;
 70                     }
 71                     r++;
 72                 }
 73             }
 74         }
 75         if(leap)
 76         break;
 77     }
 78     return ;
 79 }
 80 int main()
 81 {
 82     int i,j;
 83 
 84     while(~scanf("%d %d",&m,&n))
 85     {
 86         leap = flag = 0;
 87         memset(map,0,sizeof(map));
 88 
 89         for(i = 0;i < m;i++)
 90         scanf("%s",map[i]);
 91 
 92         for(i = 0;i < m;i++)
 93         {
 94             for(j = 0;j < n;j++)
 95             {
 96                 if(map[i][j] == 'a')//找到入口
 97                 {
 98                     flag = 1;
 99                     bfs(i,j);
100                     break;
101                 }
102             }
103             if(flag)
104             break;
105 
106         }
107         if(leap)
108         printf("%d\n",q[r].step);
109         else
110         puts("Poor ANGEL has to stay in the prison all his life.");
111     }
112     return 0;
113 }

  1 #include <stdio.h>
  2 #include <iostream>
  3 #include <string.h>
  4 
  5 using namespace std;
  6 
  7 int vis[10005];
  8 int prim[10005],leap;
  9 struct node
 10 {
 11     int n[5],step;
 12     int num;
 13 }q[4*10005];
 14 void make_prim()
 15 {
 16     memset(prim,0,sizeof(prim));
 17     int flag = 1,i,j;
 18     for(i = 1001;i <= 9999;i += 2)
 19     {
 20         flag = 1;
 21         for(j = 2;j <= i/2;j++)
 22         {
 23             if(i%j == 0)
 24             {
 25                 flag = 0;
 26                 break;
 27             }
 28         }
 29         prim[i] = flag;
 30 
 31     }
 32 }
 33 int num,f,r,target;
 34 void get()
 35 {
 36     int n;
 37     n = q[f].num;
 38 
 39     q[f].n[4] = n%10;
 40     n /= 10;
 41     q[f].n[3] = n%10;
 42     n /= 10;
 43     q[f].n[2] = n%10;
 44     n /= 10;
 45     q[f].n[1] = n;
 46 }
 47 int getsum(struct node temp)
 48 {
 49     return temp.n[1]*1000+temp.n[2]*100+temp.n[3]*10+temp.n[4];
 50 }
 51 void bfs()
 52 {
 53     int i,j;
 54     memset(vis,0,sizeof(vis));
 55     f = r = 0;
 56     q[r].num = num;
 57     q[r].step = 0;
 58     get();
 59     r++;
 60     vis[num] = 1;
 61     leap = 0;
 62     while(f < r)
 63     {
 64         struct node temp,now;
 65         get();
 66         now  = q[f];
 67         now.step = q[f].step+1;
 68         f++;
 69         for(i = 0;i < 10;i++)
 70         {
 71             for(j = 1;j < 5;j++)
 72             {
 73                 temp = now;
 74                 if(i != temp.n[j])
 75                 {
 76                     temp.n[j] = i;
 77                     temp.num = getsum(temp);
 78 
 79                     if(!vis[temp.num] && prim[temp.num])
 80                     {
 81                         vis[temp.num] = 1;
 82                         q[r] = temp;
 83                         if(temp.num == target)
 84                         {
 85                             leap = 1;
 86                             break;
 87                         }
 88                         r++;
 89                     }
 90                 }
 91             }
 92             if(leap)
 93             break;
 94         }
 95         if(leap)
 96         break;
 97     }
 98     return ;
 99 }
100 int main()
101 {
102     int t;
103     make_prim();
104     scanf("%d",&t);
105 
106     while(t--)
107     {
108         scanf("%d %d",&num,&target);
109         if(num == target)
110         {
111             puts("0");
112             continue;
113         }
114 
115         bfs();
116         if(leap)
117         printf("%d\n",q[r].step);
118         else
119         printf("Impossible\n");
120 
121     }
122 
123     return 0;
124 }