hdu诡异的楼梯(BFS+优先队列）

http://acm.hdu.edu.cn/showproblem.php?pid=1180

这题交了7次悲剧了前几次因为把+行想成是左右走了一直WA 后来看出来了又把走过的楼梯给标记了这里的楼梯不能标记

因为可以在原地等着楼梯转变加的时间有可能是2 这样普通队列满足不了最少的先搜就用优先队列了

View Code

  1 #include<stdio.h>
  2 #include<string.h>
  3 typedef struct node
  4 {
  5  int x,y,num;
  6 }st;
  7 int f[22][22];
  8 char c[22][22];
  9 st q[10001],t;
 10 int d,p;
 11 void sort()//把用时少的优先放在队首
 12 {
 13  int i;
 14  for(i = d ; i > p ; i--)
 15  {
 16   if(q[i].num<q[i-1].num)
 17   {
 18    t = q[i];
 19    q[i] = q[i-1];
 20    q[i-1] = t;
 21   }
 22   else
 23   break;
 24  }
 25 }
 26 void inque(int a,int b)
 27 {
 28  d++;
 29  q[d].x = a;
 30  q[d].y = b;
 31 }
 32 int main()
 33 {
 34  int n,m,i,j,x[2],y[2],dis[2] = {-1,1};
 35  while(scanf("%d%d%*c", &n,&m)!=EOF)
 36  {
 37   memset(f,0,sizeof(f));
 38   for(i = 1 ; i <= n ; i++)
 39   {
 40    for(j = 1 ; j <= m ; j++)
 41    {
 42     scanf("%c",&c[i][j]);
 43     if(c[i][j] == 'S')
 44     {
 45      x[0] = i;
 46      y[0] = j;
 47     }
 48     if(c[i][j] == 'T')
 49     {
 50      x[1] = i;
 51      y[1] = j;
 52     }
 53    }
 54    getchar();
 55   }
 56   d = 0;
 57   p = 0;
 58   q[1].num = 0;
 59   f[x[0]][y[0]] = 1;
 60   inque(x[0],y[0]);
 61   do
 62   {
 63    p++;
 64    int px = q[p].x;
 65    int py = q[p].y;
 66    if(px==x[1]&&py==y[1])
 67     break;
 68    int pf = q[p].num%2;
 69    for(i = 0 ; i < 2 ; i++)
 70    {
 71     int qx = px+dis[i];
 72     int qy = py+dis[i];
 73     if(!f[qx][py]&&qx>0&&qx<=n&&(c[qx][py]=='.'||c[qx][py]=='|'||c[qx][py]=='-'||c[qx][py]=='T'))
 74     {
 75      if(c[qx][py]=='|'||c[qx][py]=='-')
 76      {
 77       if(!f[qx+dis[i]][py]&&qx+dis[i]>0&&qx+dis[i]<=n&&(c[qx+dis[i]][py]=='.'||c[qx+dis[i]][py]=='T'))
 78       {
 79        inque(qx+dis[i],py);
 80        if((!pf&&c[qx][py]=='|')||(pf&&c[qx][py]=='-'))
 81        {
 82         q[d].num = q[p].num+1;
 83         sort();
 84        }
 85        else
 86        {
 87         q[d].num = q[p].num+2;
 88         sort();
 89        }
 90        f[qx+dis[i]][py] = 1;
 91       }
 92      }
 93      else
 94      {
 95       f[qx][py] = 1;
 96       inque(qx,py);
 97       {
 98        q[d].num = q[p].num+1;
 99        sort();
100       }
101       f[qx][py] = 1;
102      }
103     }
104     if(!f[px][qy]&&qy>0&&qy<=m&&(c[px][qy]=='.'||c[px][qy]=='|'||c[px][qy]=='-'||c[px][qy]=='T'))
105     {
106      if(c[px][qy]=='|'||c[px][qy]=='-')
107      {
108       if(!f[px][qy+dis[i]]&&qy+dis[i]>0&&qy+dis[i]<=m&&(c[px][qy+dis[i]]=='.'||c[px][qy+dis[i]]=='T'))
109       {
110        inque(px,qy+dis[i]);
111        if((!pf&&c[px][qy]=='|')||(pf&&c[px][qy]=='-'))
112        {
113         q[d].num = q[p].num+2;
114         sort();
115        }
116        else
117        {
118         q[d].num = q[p].num+1;
119         sort();
120        }
121        f[px][qy+dis[i]] = 1;
122       }
123      }
124      else
125      {
126       f[px][qy] = 1;
127       inque(px,qy);
128       {
129        q[d].num = q[p].num+1;
130        sort();
131       }
132       f[px][qy] = 1;
133      }
134     }
135    }
136   }while(d!=p);
137   printf("%d\n",q[p].num);
138  }
139  return 0;
140 }