简答题 偏难
#7250

玩具摆放 在一个4*4的方框内摆放了若干个相同的玩具。 某人想通过移动玩具,将这些玩具重新摆放成为他心中理想的状态。要求每次移动时,只能将某一个玩具向上下左右四…

玩具摆放

在一个4*4的方框内摆放了若干个相同的玩具。

某人想通过移动玩具,将这些玩具重新摆放成为他心中理想的状态。要求每次移动时,只能将某一个玩具向上下左右四个方向之一移动一步。不能将玩具移出方框,并且移动的目标位置不能已经放置有玩具。

请你用最少的移动次数将初始的玩具状态移动到他心中的目标状态。

时间限制:10000

内存限制:524288

输入

前4行表示玩具的初始状态,每行4个数字1或0,1表示方格中放置了玩具,0表示没有放置玩具。 接着是一个空行。接下来4行表示玩具的目标状态,每行4个数字1或0,意义同上。

输出

一个整数,所需要的最少移动次数。保证初始状态可以达到目标状态。

样例输入

1111
0000
1110
0010

1010
0101
1010
0101

样例输出

4

提示

可以考虑将玩具局面表示为一个16 bit的整数,设置一个标志数组用来判重,用这个整数做下标找其对应标志位

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;queue&gt; #include &lt;stack&gt; #include &lt;vector&gt; // #include&lt;cmath&gt; using namespace std; const int INF = 9999999; #define LL long long inline int read() {   int x = 0, f = 1;   char c = getchar();   for (; !isdigit(c); c = getchar())     if (c == '-')       f = -1;   for (; isdigit(c); c = getchar())     x = x * 10 + c - '0';   return x * f; } int N, E; bool vis[65539]; char c; int l = 1, r = 1; struct data {   int st, k; } Que[700001]; void BFS() {   Que[l].st = 0, Que[l].k = N;   int step, Now;   if (Que[l].k == E) {     printf("%d", Que[l].st);     return;   }   while (l &lt;= r) {     Now = Que[l].k, step = Que[l].st;     for (int i = 1; i &lt;= 4; i++) {       for (int j = 1; j &lt;= 4; j++) {         if (((Now &gt;&gt; ((4 - i) * 4 + 4 - j)) &amp; 1)) {           for (int p = 0; p &lt; 4; p++) {             if (p == 0 &amp;&amp; i != 1 &amp;&amp;                 !((Now &gt;&gt; ((4 - (i - 1)) * 4 + 4 - j)) &amp; 1) &amp;&amp;                 !vis[Now - (1 &lt;&lt; ((4 - i) * 4 + 4 - j)) +                      (1 &lt;&lt; ((4 - i) * 4 + 8 - j))]) {               Que[++r].k = Now - (1 &lt;&lt; ((4 - i) * 4 + 4 - j)) +                            (1 &lt;&lt; ((4 - i) * 4 + 8 - j));               if (Que[r].k == E) {                 printf("%d", step + 1);                 return;               }               Que[r].st = step + 1;               vis[Que[r].k] = 1;             }             if (p == 1 &amp;&amp; i != 4 &amp;&amp;                 !((Now &gt;&gt; ((4 - (i + 1)) * 4 + 4 - j)) &amp; 1) &amp;&amp;                 !vis[Now - (1 &lt;&lt; ((4 - i) * 4 + 4 - j)) +                      (1 &lt;&lt; ((4 - i) * 4 - j))]) {               Que[++r].k =                   Now - (1 &lt;&lt; ((4 - i) * 4 + 4 - j)) + (1 &lt;&lt; ((4 - i) * 4 - j));               if (Que[r].k == E) {                 printf("%d", step + 1);                 return;               }               Que[r].st = step + 1;               vis[Que[r].k] = 1;             }             if (p == 2 &amp;&amp; j != 1 &amp;&amp;                 !((Now &gt;&gt; ((4 - i) * 4 + 4 - (j - 1))) &amp; 1) &amp;&amp;                 !vis[(1 &lt;&lt; ((4 - i) * 4 + 4 - j)) +                      (1 &lt;&lt; ((4 - i) * 4 + 4 - (j - 1)))]) {               Que[++r].k = Now - (1 &lt;&lt; ((4 - i) * 4 + 4 - j)) +                            (1 &lt;&lt; ((4 - i) * 4 + 4 - (j - 1)));               if (Que[r].k == E) {                 printf("%d", step + 1);                 return;               }               Que[r].st = step + 1;               vis[Que[r].k] = 1;             }             if (p == 3 &amp;&amp; j != 4 &amp;&amp;                 !((Now &gt;&gt; ((4 - i) * 4 + 4 - (j + 1))) &amp; 1) &amp;&amp;                 !vis[Now - (1 &lt;&lt; ((4 - i) * 4 + 4 - j)) +                      (1 &lt;&lt; ((4 - i) * 4 + 4 - (j + 1)))]) {               Que[++r].k = Now - (1 &lt;&lt; ((4 - i) * 4 + 4 - j)) +                            (1 &lt;&lt; ((4 - i) * 4 + 4 - (j + 1)));               if (Que[r].k == E) {                 printf("%d", step + 1);                 return;               }               Que[r].st = step + 1;               vis[Que[r].k] = 1;             }           }         }       }     }     l++;   } } int main() {   // freopen(".in","r",stdin);   // freopen(".out","w",stdout);   int tmp = 16;   for (int i = 1; i &lt;= 4; i++)     for (int j = 1; j &lt;= 4; j++) {       cin &gt;&gt; c;       N = N + (1 &lt;&lt; (tmp - 1)) * (c - '0');       tmp--;     }   vis[N] = true;   tmp = 16;   for (int i = 1; i &lt;= 4; i++)     for (int j = 1; j &lt;= 4; j++) {       cin &gt;&gt; c;       E = E + (1 &lt;&lt; (tmp - 1)) * (c - '0');       tmp--;     }   BFS();   return 0; }</pre>
这道题暂未补解析。