m0_73468354 2022-11-01 16:33 采纳率: 50%
浏览 36
已结题

信息学一本通(1451:棋盘游戏)

输出结果不对 大家看看哪错了

今日程序内容:
棋盘游戏。在一个4 x 4的棋盘上有 8个黑棋和 8个白棋,当且仅当两个格子有公共边,这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。给出一个初始棋盘和一个最终棋盘,请找出一个最短的移动序列使初始棋盘变为最终棋盘。

  • 输入:
    前四行,每行4个数字( 1或者0 ),描述了初始棋盘;接着是一个空行;
    第六到第九行,每行 4个数字( 1或者0),描述了最终棋盘。
    
  • 输出:
    输出的第一行是一个整数n,表示最少的移动步数。
    

#include <stdio.h>
int A,B;
int vis[100000];
struct P
{
int num,d;
};
struct P p[100];
void bfs()
{
p[0].num=A,p[0].d=0;
while(p[0].num!=0)
{
int tmp=p[0].num;
int k=0;
if(tmp==B)
{
printf("%d\n",p[0].d);
return;
}
for(int i=15;i>=0;i--)
{
int x=(15-i)/4,y=(15-i)%4,w=1<<i,z;
if(y<3&&(tmp&(1<<i))!=(tmp&(1<<(i-1))))
{
z=1<<(i-1);
if(!vis[tmp^z^w])
{
vis[tmp^z^w]=1;
p[k++].num=tmp^z^w;
p[k++].d=p[0].d+1;
}
}
if(x<3&&(tmp&(1<<i))!=(tmp&(1<<(i-4))))
{
z=1<<(i-4);
if(!vis[tmp^z^w])
{
vis[tmp^z^w]=1;
p[k++].num=tmp^z^w;
p[k++].d=p[0].d+1;
}
}
}
}
}
int main()
{
int i;
char ch;
for(i=15;i>=0;i--)
{
scanf("%c",&ch);

    if(ch=='1')
    {
        A+=1<<i;
    }
}
getchar();
for(i=15;i>=0;i--)
{
    scanf("%c",&ch);
    if(ch=='1')
    {
        B+=1<<i;
    }
}
printf("%d %d",A,B);
if(A==B)
{
    printf("0\n");
}
else
{
    bfs();
}
return 0;

}

  • 写回答

1条回答 默认 最新

  • .LAL. C/C++领域新星创作者 2022-11-01 16:38
    关注
    
    #include<iostream>
    #include<cstdio>
    #include<cstdlib>
    #include<string>
    #include<cstring>
    #include<cmath>
    #include<ctime>
    #include<algorithm>
    #include<utility>
    #include<stack>
    #include<queue>
    #include<vector>
    #include<set>
    #include<map>
    #include<bitset>
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LL long long
    #define Pair pair<int,int>
    LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; }
    LL multMod(LL a,LL b,LL mod){ a%=mod; b%=mod; LL res=0; while(b){if(b&1)res=(res+a)%mod; a=(a<<=1)%mod; b>>=1; } return res%mod;}
    LL quickMultPowMod(LL a, LL b,LL mod){ LL res=1,k=a; while(b){if((b&1))res=multMod(res,k,mod)%mod; k=multMod(k,k,mod)%mod; b>>=1;} return res%mod;}
    LL quickPowMod(LL a,LL b,LL mod){ LL res=1; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1; } return res; }
    LL getInv(LL a,LL mod){ return quickPowMod(a,mod-2,mod); }
    LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); }
    LL LCM(LL x,LL y){ return x/GCD(x,y)*y; }
    const double EPS = 1E-6;
    const int MOD = 1000000000+7;
    const int N = 1000+5;
    const int dx[] = {0,0,-1,1,1,-1,1,1};
    const int dy[] = {1,-1,0,0,-1,1,-1,1};
    using namespace std;
     
    struct Node {
        int val;
        int step;
        Node() {}
        Node(int val, int step) : val(val), step(step) {}
    };
    int vis[65536 + 10];
    void BFS(Node st, Node ed) {
        memset(vis, 0, sizeof(vis));
        queue<Node> Q;
        Q.push(st);
        while (!Q.empty()) {
            Node now = Q.front();
            Q.pop();
            if (now.val == ed.val) {
                cout << now.step << endl;
                return;
            }
     
            int val = now.val;
            int step = now.step;
            for (int i = 15; i >= 0; i--) { //从高到低枚举每一位
                int x = (15 - i) / 4, y = (15 - i) % 4; //横纵坐标
                int nowPos = 1 << i; //当前位置代表权值
                int rightPos = 1 << (i - 1); //当前位置右方位置代表权值
                int downPos = 1 << (i - 4);  //当前位置下方位置代表权值
                if (y < 3 && ((val & nowPos) != (val & rightPos))) { //向右交换
                    int nextVal = val ^ nowPos ^ rightPos; //交换后的状态
                    if (!vis[nextVal]) {
                        vis[nextVal] = true;
                        Q.push(Node(nextVal, step + 1));
                    }
                }
                if (x < 3 && ((val & nowPos) != (val & downPos))) { //向下交换
                    int nextVal = val ^ nowPos ^ downPos; //交换后的状态
                    if (!vis[nextVal]) {
                        vis[nextVal] = true;
                        Q.push(Node(nextVal, step + 1));
                    }
                }
            }
        }
    }
    int main() {
        char ch;
        int st = 0, ed = 0;
        for (int i = 15; i >= 0; i--) {
            cin >> ch;
            if (ch == '1')
                st += 1 << i;
        }
        for (int i = 15; i >= 0; i--) {
            cin >> ch;
            if (ch == '1')
                ed += 1 << i;
        }
        if (st == ed)
            printf("0\n");
        else
            BFS(Node(st, 0), Node(ed, 0));
        return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 11月11日
  • 已采纳回答 11月3日
  • 创建了问题 11月1日

悬赏问题

  • ¥15 关于模型训练的一个问题
  • ¥15 装了几千台服务器从来没遇到这种问题,哎看下哪位帮我解决吧
  • ¥15 单片机程序上的困难问题
  • ¥15 请教某软件缓存Ts文件破解合并mp4的方法
  • ¥15 求小游戏炸弹人中关于敌人的C++代码
  • ¥15 拿到这个服务器最高权限有偿
  • ¥50 来个抓app跳转支付宝转链接的
  • ¥15 remotes安装提示没有description文件
  • ¥15 AttributeError: 'NoneType' object has no attribute 'drop_duplicates'报错
  • ¥15 以下代码,运行结果报错