sdut2465其实玩游戏也得学程序(bfs+优先队列）

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2465
View Code
  1 #include <iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<queue>
  5 using namespace std;
  6 typedef struct node
  7 {
  8     int x1,y1,x,y,num,flag1;
  9     friend bool operator<( struct node a, struct node b )
 10     {
 11          return a.num>b.num;
 12     }
 13     int flag;
 14 }st;
 15 st q[100000];
 16 char w[110][110];
 17 int n,m,f[110][110],kj[100000];
 18 int judge(int x,int y)
 19 {
 20     if(x>=n||y>=m||x<0||y<0)
 21     return 0;
 22     if(w[x][y]=='X')
 23     return 0;
 24     return 1;
 25 }
 26 void bfs()
 27 {
 28     int flag= 0,k,g=0,i,j,ii,kk=0,di[4][2] = {0,1,0,-1,1,0,-1,0},p;
 29     priority_queue <st> qq;
 30     st mm,nn;
 31     memset(f,0,sizeof(f));
 32     mm.x = 0;mm.y = 0;mm.num = 0;mm.flag1 = 1;
 33     kk++;
 34     qq.push(mm);
 35     f[0][0] = 1;
 36     while(!qq.empty())
 37     {
 38 
 39         nn = qq.top();
 40         int tx = nn.x;
 41         int ty = nn.y;
 42         p = nn.flag1;
 43         int tnum = nn.num;
 44         qq.pop();
 45         if(tx==n-1&&ty==m-1)
 46         {
 47             flag = 1;
 48             break;
 49         }
 50         for(ii= 0 ; ii < 4 ; ii++)
 51         {
 52             int i = tx+di[ii][0];
 53             int j = ty+di[ii][1];
 54             if(!f[i][j]&&judge(i,j))
 55             {
 56                 f[i][j] = 1;
 57                 if(w[i][j]=='.')
 58                 {
 59                     mm.x = i;mm.y = j;mm.x1 = tx; mm.y1 = ty;
 60                     mm.num = tnum+1;
 61                     mm.flag = p;
 62                     kk++;
 63                     mm.flag1= kk;
 64                     qq.push(mm);
 65                     q[kk] = mm;
 66                 }
 67                 else
 68                 {
 69                     mm.x = i;mm.y = j;mm.x1 = tx;mm.y1 = ty;
 70                     mm.num = tnum+w[i][j]-'0'+1;
 71                     mm.flag = p;
 72                     kk++;
 73                     mm.flag1 = kk;
 74                     qq.push(mm);
 75                     q[kk] = mm;
 76                 }
 77             }
 78         }
 79     }
 80     if(flag==0)
 81     printf("GAME OVER.\n");
 82     else
 83     {
 84          k = p;
 85          g++;
 86          kj[g] = p;
 87          while(q[k].flag!=1)
 88          {
 89             g++;
 90             kj[g] = q[k].flag;
 91             k = kj[g];
 92          }
 93          for(i = g ; i >= 1 ; i--)
 94          {
 95              int y = kj[i];
 96              if(w[q[y].x][q[y].y]=='.')
 97              printf("%ds:(%d,%d)->(%d,%d)\n",q[y].num,q[y].x1,q[y].y1,q[y].x,q[y].y);
 98              else
 99              {
100                  int nn = w[q[y].x][q[y].y]-'0';
101                  printf("%ds:(%d,%d)->(%d,%d)\n",q[y].num-nn,q[y].x1,q[y].y1,q[y].x,q[y].y);
102                  for(j = 1; j <= nn ; j++)
103                  printf("%ds:FIGHT AT (%d,%d)\n",q[y].num-nn+j,q[y].x,q[y].y);
104              }
105          }
106     }
107 }
108 int main()
109 {
110     int i,j,k;
111     while(cin>>n>>m)
112     {
113         if(n==0&&m==0)
114         break;
115         getchar();
116         for(i = 0 ; i < n ; i++)
117         for(j = 0 ; j < m ; j++)
118         cin>>w[i][j];
119         bfs();
120         printf("FINISH\n");
121     }
122     return 0;
123 }