魔法少女リリカルなのは

43618 ワード

転入先http://www.cnblogs.com/whatbeg/p/3728557.html
直接BFSは絶対にだめで、複雑度が高すぎる.
加算減算操作は考慮しないでください.なぜなら、それらは関連していないので、よく処理されています.
最初は魔棒が左端だったので、i番目の位置が訪問されると、前のきっと訪問したことがあります.同時に、最後の人と交換することで、最後の人に直接アクセスすることができます.したがって、すべてのアクセスされた状態(符号)は、1、12、123、1234、12345、123456、16、126、1236、12346のみであり、10個である.
したがって状態記録はdis[6][6][6][6][6][10]であり、上位6人は現在のi位が元のj位、7人目6人は杖が現在どこにあるか、10人はどの位置が訪問されたかを表す.
disは現在の状態までのステップ数(最小)を表す.
BFSが出た後、6桁の各ビットとポインタ位置と10種類の状態を列挙し、この状態がアクセスされているかどうかを見て、アクセスされている場合は、この状態に到達できることを示し、その後、この状態から目標状態までどれだけのステップ(達成できない可能性がある)が必要かを見て、dis[状態]+ステップ数が最小ステップ数より小さいかどうかを見て、答えを更新します.
 
  1 #include <iostream>

  2 #include <cstdio>

  3 #include <cstring>

  4 #include <cmath>

  5 #include <algorithm>

  6 #include <queue>

  7 #define Mod 1000000007

  8 #define INT 2147483647

  9 using namespace std;

 10 #define N 50007

 11 

 12 struct node

 13 {

 14     int p[7];

 15     int point,state;

 16     int step;

 17 }S;

 18 

 19 void Popy(int *p1,int *p2)

 20 {

 21     for(int i=1;i<7;i++)

 22         p1[i] = p2[i];

 23 }

 24 

 25 int dis[7][7][7][7][7][7][7][10];

 26 int E[7],SS[7];

 27 

 28 int min(int ka,int kb)

 29 {

 30     if(ka < kb)

 31         return ka;

 32     return kb;

 33 }

 34 

 35 int max(int ka,int kb)

 36 {

 37     if(ka > kb)

 38         return ka;

 39     return kb;

 40 }

 41 

 42 void BFS(node S)

 43 {

 44     queue<node> que;

 45     memset(dis,-1,sizeof(dis));

 46     que.push(S);

 47     dis[S.p[1]][S.p[2]][S.p[3]][S.p[4]][S.p[5]][S.p[6]][1][0] = 0;

 48     while(!que.empty())

 49     {

 50         node tmp = que.front();

 51         que.pop();

 52         for(int i=0;i<4;i++)

 53         {

 54             node now;

 55             if(i == 0)   //     

 56             {

 57                 swap(tmp.p[1],tmp.p[tmp.point]);

 58                 Popy(now.p,tmp.p);

 59                 swap(tmp.p[1],tmp.p[tmp.point]);

 60                 now.point = tmp.point;

 61                 now.state = tmp.state;

 62                 now.step = tmp.step + 1;

 63                 if(dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] == -1 || (dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] != -1 && now.step < dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state]))

 64                 {

 65                     dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] = now.step;

 66                     que.push(now);

 67                 }

 68             }

 69             else if(i == 1)   //     

 70             {

 71                 swap(tmp.p[6],tmp.p[tmp.point]);

 72                 Popy(now.p,tmp.p);

 73                 swap(tmp.p[6],tmp.p[tmp.point]);

 74                 now.point = tmp.point;

 75                 if(tmp.state <= 3)

 76                     now.state = tmp.state + 6;

 77                 else if(tmp.state == 4)

 78                     now.state = tmp.state + 1;

 79                 else

 80                     now.state = tmp.state;

 81                 now.step = tmp.step + 1;

 82                 if(dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] == -1 || (dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] != -1 && now.step < dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state]))

 83                 {

 84                     dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] = now.step;

 85                     que.push(now);

 86                 }

 87             }

 88             else if(i == 2)   //  

 89             {

 90                 Popy(now.p,tmp.p);

 91                 now.point = max(1,tmp.point-1);

 92                 now.state = tmp.state;

 93                 now.step = tmp.step + 1;

 94                 if(dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] == -1 || (dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] != -1 && now.step < dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state]))

 95                 {

 96                     dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] = now.step;

 97                     que.push(now);

 98                 }

 99             }

100             else if(i == 3)  //  

101             {

102                 Popy(now.p,tmp.p);

103                 now.point = min(6,tmp.point+1);

104                 if(tmp.state < 5)

105                     now.state = tmp.state+1;

106                 else if(tmp.state == 5)

107                     now.state = tmp.state;

108                 else if(tmp.state < 9)

109                     now.state = tmp.state+1;

110                 else

111                     now.state = tmp.state-4;

112                 now.step = tmp.step + 1;

113                 if(dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] == -1 || (dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] != -1 && now.step < dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state]))

114                 {

115                     dis[now.p[1]][now.p[2]][now.p[3]][now.p[4]][now.p[5]][now.p[6]][now.point][now.state] = now.step;

116                     que.push(now);

117                 }

118             }

119         }

120     }

121 }

122 

123 int main()

124 {

125     int a,b,i;

126     int h[7];

127     int pot,status;

128     while(scanf("%d%d",&a,&b)!=EOF)

129     {

130         S.p[1] = 1;   //

131         S.p[2] = 2;

132         S.p[3] = 3;

133         S.p[4] = 4;

134         S.p[5] = 5;

135         S.p[6] = 6;

136         S.point = 1;

137         S.state = 0;

138         S.step = 0;

139         SS[1] = (a/100000)%10;

140         SS[2] = (a/10000)%10;

141         SS[3] = (a/1000)%10;

142         SS[4] = (a/100)%10;

143         SS[5] = (a/10)%10;

144         SS[6] = a%10;

145         E[1] = (b/100000)%10;

146         E[2] = (b/10000)%10;

147         E[3] = (b/1000)%10;

148         E[4] = (b/100)%10;

149         E[5] = (b/10)%10;

150         E[6] = b%10;

151         BFS(S);

152         int ans = Mod;

153         for(h[1]=1;h[1]<=6;h[1]++)

154         {

155             for(h[2]=1;h[2]<=6;h[2]++)

156             {

157                 if(h[2] != h[1])

158                 {

159                     for(h[3]=1;h[3]<=6;h[3]++)

160                     {

161                         if(h[3] != h[2] && h[3] != h[1])

162                         {

163                             for(h[4]=1;h[4]<=6;h[4]++)

164                             {

165                                 if(h[4] != h[1] && h[4] != h[2] && h[4] != h[3])

166                                 {

167                                     for(h[5]=1;h[5]<=6;h[5]++)

168                                     {

169                                         if(h[5] != h[1] && h[5] != h[2] && h[5] != h[3] && h[5] != h[4])

170                                         {

171                                             for(h[6]=1;h[6]<=6;h[6]++)

172                                             {

173                                                 if(h[6] != h[1] && h[6] != h[2] && h[6] != h[3] && h[6] != h[4] && h[6] != h[5])

174                                                 {

175                                                     for(pot=1;pot<=6;pot++)

176                                                     {

177                                                         for(status=0;status<10;status++)

178                                                         {

179                                                             if(dis[h[1]][h[2]][h[3]][h[4]][h[5]][h[6]][pot][status] != -1)

180                                                             {

181                                                                 int cnt = 0;

182                                                                 int t,r;

183                                                                 int flag = 1;                      //No.  status

184                                                                 if(status <= 5)                    //1    1

185                                                                 {                                  //2    12

186                                                                     for(t=1;t<=status+1;t++)       //3    123

187                                                                         cnt += abs(E[t]-SS[h[t]]); //4    1234

188                                                                     for(t;t<=6;t++)                //5    12345

189                                                                         if(E[t] != SS[h[t]])       //6    123456

190                                                                         {                          //7    16

191                                                                             flag = 0;              //8    126

192                                                                             break;                 //9    1236

193                                                                         }                          //10   12346

194                                                                     if(!flag)

195                                                                         continue;

196                                                                 }

197                                                                 else if(status >= 6 && status <= 9)

198                                                                 {

199                                                                     for(r=1;r<=status-5;r++)

200                                                                         cnt += abs(E[r]-SS[h[r]]);

201                                                                     for(r;r<6;r++)

202                                                                         if(E[r] != SS[h[r]])

203                                                                         {

204                                                                             flag = 0;

205                                                                             break;

206                                                                         }

207                                                                     if(!flag)

208                                                                         continue;

209                                                                     cnt += abs(E[6]-SS[h[6]]);

210                                                                 }

211                                                                 ans = min(ans,dis[h[1]][h[2]][h[3]][h[4]][h[5]][h[6]][pot][status]+cnt);

212                                                             }

213                                                         }

214                                                     }

215                                                 }

216                                             }

217                                         }

218                                     }

219                                 }

220                             }

221                         }

222                     }

223                 }

224             }

225         }

226         printf("%d
",ans); 227 } 228 return 0; 229 }