HDU 3681 Prison Break（状態圧縮dp＋BFS）

テーマリンク：http://acm.hdu.edu.cn/showproblem.php?pid=3681
先日時間をかけて見たテーマですが、書けませんでした。弱くて諦めました。今の後輩がこんなコードを書いてくれたとは思いませんでした。ここで彼の成果を借りて、よく勉強してください。
Sample Input
5
GDDSS
SSSFS
SYGYS
SGS YS
SSYSS
0
 
Sample Output
4
マトリックス（刑務所として）と電池を入れたロボットが刑務所にいます。

Fは出発点で、図中は一つしかなく、初期状態ではロボットはここで電池がいっぱいです。

Dは障害物ですので、歩いてはいけません。

Sはスペースです。マシンは自由に通過できます。

Gは充電ポイントで、一回しか充電できません。一回は電池がいっぱいになります。Gを通してSとして充電しないと、充電後GはSになります。

Y点はスイッチで、ロボットが通過し、かつ通過してSになります。

ロボットはYを全部通して、刑務所から逃げられます。これまでは一つの格子（上、下、左、右）だけで移動できました。そして一マスごとに電池の電池量を消耗しました。電池がないと移動できません。バッテリーがフル充電されている状態で、少なくとも何本の電気が彼を刑務所から脱出させることができますか？
この問題の考え方はそのデータから来ています。Y+Gの数は15より小さいです。ここからは状態圧縮DPが考えられます。
電気量の求め方は二分検索です。
全体図は明らかに処理しなければなりません。Y、Fはお互いに接続しなければなりません。接続しないと、明らかに無解です。逆に必ず解があります。Y，F，Gに対応する番号を、始点Fを0，Y，Gを順に番号付けし、YとGを2つの番号に分けると、次はゲートYと充電ポイントGの判断が容易になり、番号範囲を直接判断すれば良い。
次は各点に対する最短のショートを求めて、更に最短のショートを求めた後、Yを発見すれば、F間のある2点がつながりません。解がなければ、解がありません。
解があれば、状態圧縮DPを行い、各maxt（現在のバッテリのフルバッテリ量）に対して、途中でmaxtより大きいと更新できないので、いずれにしても判断して更新することができる。各Y点がすでにエルゴードされている場合、この状態で実行可能かどうかを判断し、可能であればTRUEに戻る。
 
コードは以下の通りです

  1 #include<algorithm>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<queue>
  6 using namespace std;
  7 const int INF=1<<29;
  8 int as[600000];
  9 void st()
 10 {
 11     int i, k=0;
 12     for(i=1; i<600000; i*=2)
 13     {
 14         as[i]=++k;
 15     }
 16 }
 17 struct Node
 18 {
 19     int x, y;
 20 } nod[17];
 21 struct POS
 22 {
 23     POS() {}
 24     POS(int a,int b,int c)
 25     {
 26         x=a,y=b,now=c;
 27     }
 28     int x, y, now;
 29 } pos;
 30 int n, m, p, q, sx, sy;
 31 int dis[17][17], dp[600000][17], the[17][17], num, ll;
 32 char map[17][17];
 33 bool ans;
 34 void init()            //   Y,F,G  
 35 {
 36     int i, j;
 37     memset(the,-1,sizeof(the));
 38     p=1;
 39     for(i=0; i<n; i++)
 40     {
 41         for(j=0; j<m; j++)
 42         {
 43             if(map[i][j]=='F')
 44                 sx=i, sy=j;
 45             if(map[i][j]=='Y')
 46             {
 47                 nod[p].x=i, nod[p].y=j;
 48                 the[i][j]=p;   //                 
 49                 p++;
 50             }
 51         }
 52     }
 53     q=p;
 54     for(i=0; i<n; i++)
 55         for(j=0; j<m; j++)
 56         {
 57             if(map[i][j]=='G')
 58             {
 59                 nod[q].x=i, nod[q].y=j;
 60                 the[i][j]=q;
 61                 q++;
 62             }
 63         }
 64     nod[0].x=sx, nod[0].y=sy;
 65     the[sx][sy]=0;
 66     for(i=0; i<q; i++)
 67         for(j=0; j<q; j++)
 68         {
 69             if(i==j)
 70                 dis[i][j]=0;
 71             else dis[i][j]=INF;
 72         }
 73 }
 74 int dx[]= {1,0,-1,0};
 75 int dy[]= {0,1,0,-1};
 76 bool can(int x,int y)
 77 {
 78     if(x<0||x>=n||y<0||y>=m||map[x][y]=='D')
 79         return false;
 80     return true;
 81 }
 82 void bfs()        //BFS Y,F,G      
 83 {
 84     int i, j, nx, ny, x, y, now;
 85     POS tmp;
 86     bool vis[17][17];
 87     for(i=0; i<q; i++)
 88     {
 89         memset(vis,0,sizeof(vis));
 90         queue<POS> qq;
 91         qq.push(POS(nod[i].x,nod[i].y,0));
 92         while(!qq.empty())
 93         {
 94             tmp=qq.front();
 95             qq.pop();
 96             x=tmp.x, y=tmp.y, now=tmp.now;
 97             for(j=0; j<4; j++)
 98             {
 99                 nx=x+dx[j], ny=y+dy[j];
100                 if(can(nx,ny)&&!vis[nx][ny])
101                 {
102                     if(the[nx][ny]!=-1)
103                         dis[i][the[nx][ny]]=now+1;
104                     vis[nx][ny]=true;
105                     qq.push(POS(nx,ny,now+1));
106                 }
107             }
108         }
109     }
110     for(i=0; i<p; i++)
111         for(j=0; j<p; j++)
112             if(dis[i][j]==INF) ans=false;
113 }
114 bool deal(int maxt)        //    DP      
115 {
116     int i, j, k, tmp;
117     for(i=0; i<num; i++)
118         for(j=0; j<q; j++)
119             dp[i][j]=INF;
120     dp[0][0]=0;
121     int ed;
122     for(i=1; i<num; i++)
123     {
124         for(j=i; j>0; j-=j&(-j))
125         {
126             tmp=j&(-j);
127             ed=as[tmp];
128             for(k=0; k<q; k++)
129                 if(dp[i^tmp][k]+dis[k][ed]<=maxt)
130                     dp[i][ed]=min(dp[i^tmp][k]+dis[k][ed],dp[i][ed]);
131             if(ed>=p&&dp[i][ed]!=INF)
132                 dp[i][ed]=0;
133             if(dp[i][ed]!=INF)
134             {
135                 for(k=0; k<p; k++)
136                 {
137                     if(dp[i][ed]+dis[ed][k]<=maxt)
138                         dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],dp[i][ed]+dis[ed][k]);
139                 }
140                 for(; k<q; k++)
141                 {
142                     if((1<<(k-1))&i) continue;
143                     if(dp[i][ed]+dis[ed][k]<=maxt)
144                         dp[i|(1<<(k-1))][k]=0;
145                 }
146             }
147         }
148         if(i%ll==ll-1)
149         {
150             for(j=0; j<q; j++)
151                 if(dp[i][j]<=maxt) return true;
152         }
153     }
154     return false;
155 }
156 int main()
157 {
158     int i, j, tmp, l, r;
159     st();
160     while(scanf("%d%d",&n,&m)!=EOF)
161     {
162         if(n==0&&m==0) break;
163         for(i=0; i<n; i++)
164             scanf("%s",map[i]);
165         init();
166         ans=true;
167         bfs();
168         num=1<<(q-1);    //      
169         l=1, r=300;
170         ll=1<<(p-1);
171         if(ans)            //ans true  ，Y F        
172         {
173             while(l<r)            //    
174             {
175                 m=(l+r)>>1;
176                 if(deal(m))
177                     r=m;
178                 else l=m+1;
179             }
180         }
181         if(ans) printf("%d
",r);
182         else puts("-1");
183     }
184     return 0;
185 }