移动玩具

https://loj.ac/problem/10031

题目描述

　　在一个4×4的方格内，有若干个1，每次可以交换0、1的位置，求最少多少步移成目标状态。

思路

　　这道题和棋盘游戏似乎没有太大区别，只是0、1数量不确定，思路一样，本人就不在写了。（其实代码都一模一样）。

代码

#include <bits/stdc  .h>
using namespace std;
bool vis[70005];
int step[70005];
queue<int>q;
int main() 
{
    char s[5];
    int a=0,b=0;
    for(int i=1;i<=4;i  )
    {
        scanf(" %s",s);
        for(int j=0;j<4;j  )
            a=a*2 s[j]-‘0‘;
    }
    for(int i=1;i<=4;i  )
    {
        scanf(" %s",s);
        for(int j=0;j<4;j  )
            b=b*2 s[j]-‘0‘;
    }
    vis[a]=1;step[a]=0;
    q.push(a);
    int p;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        if(now==b)
        {
            printf("%d",step[now]);
            break ;
        }
        for(int i=0;i<16;i  )
        {
            if(i%4&&(now&(1<<i))^(now&(1<<i-1))&&!vis[p=now^(1<<i)^(1<<i-1)])
            {
                vis[p]=1;
                step[p]=step[now] 1;
                q.push(p);
            }
            if(i<12&&(now&(1<<i))^(now&(1<<i 4))&&!vis[p=now^(1<<i)^(1<<i 4)])
            {
                vis[p]=1;
                step[p]=step[now] 1;
                q.push(p);
            }
        }
    }
    return 0;
}