| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3189 人关注过本帖
标题:九宫重排
取消只看楼主 加入收藏
不再有bug
Rank: 1
等 级:新手上路
帖 子:7
专家分:3
注 册:2020-3-6
结帖率:0
收藏
已结贴  问题点数:20 回复次数:2 
九宫重排
蓝桥杯的一道题,做了半天只能通过部分。不知道问题出在哪里。求大神指点

问题描述

  如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。
图片附件: 游客没有浏览图片的权限,请 登录注册
图片附件: 游客没有浏览图片的权限,请 登录注册


  我们把第一个图的局面记为:12345678.
  把第二个图的局面记为:123.46758
  显然是按从上到下,从左到右的顺序记录数字,空格记为句点。
  本题目的任务是已知九宫的初态和终态,求最少经过多少步的移动可以到达。如果无论多少步都无法到达,则输出-1。

输入格式

  输入第一行包含九宫的初态,第二行包含九宫的终态。

输出格式

  输出最少的步数,如果不存在方案,则输出-1。

样例输入

12345678.
123.46758

样例输出

3

样例输入

13524678.
46758123.

样例输出

22


我的代码:


#include<iostream>
#include<string>
#include<queue>
#include<set>
using namespace std;
struct node{
    string s;
    int n;
    node(string ss,int m){
        s=ss;
        n=m;
    }
};
string s1,s2;
queue <node> q;
set<string> s;
void f(string& s,int x,int y){
    char ch=s[x];
    s[x]=s[y];
    s[y]=ch;
}
int find(string ss){
    int len=ss.length();
    for(int i=0;i<len;i++){
        if(ss[i]=='.')
            return i;
    }
}
int bfs(){
    q.push(node(s1,0));
    s.insert(s1);
    string s3,s4;
    int n;
    while(!q.empty()){
        s3=q.front().s;
        n=q.front().n;
        q.pop();
        int x=find(s3);
        if(x-3>=0){
            s4=s3;
            f(s4,x,x-3);   
            if(s.find(s4)==s.end()){
                if(s4==s2)
                    return n+1;
                q.push(node(s4,n+1));
                s.insert(s4);
            }
        }
        if(x-1>=0){
            s4=s3;
            f(s4,x,x-1);   
            if(s.find(s4)==s.end()){
                if(s4==s2)
                    return n+1;
                s.insert(s4);
                q.push(node(s4,n+1));
            }
        }
        if(x+3<=8){
            s4=s3;
            f(s4,x,x+3);   
            if(s.find(s4)==s.end()){
                if(s4==s2)
                    return n+1;
                s.insert(s4);
                q.push(node(s4,n+1));
            }
        }
        if(x+1<=8){
            s4=s3;
            f(s4,x,x+1);   
            if(s.find(s4)==s.end()){
                if(s4==s2)
                    return n+1;
                s.insert(s4);
                q.push(node(s4,n+1));
            }
        }
    }
    return -1;
}
int main(){
    cin>>s1>>s2;
    cout<<bfs()<<endl;
    s2=s1;
    return 0;
}

谢谢了


搜索更多相关主题的帖子: return string node find int 
2020-03-06 22:13
不再有bug
Rank: 1
等 级:新手上路
帖 子:7
专家分:3
注 册:2020-3-6
收藏
得分:0 
回复 2楼 xianfajushi
不知道,程序给的样例就是这么多
2020-03-07 10:24
不再有bug
Rank: 1
等 级:新手上路
帖 子:7
专家分:3
注 册:2020-3-6
收藏
得分:0 
回复 10楼 return_0
那我的代码或者思路哪里有问题呢
2020-03-07 12:02
快速回复:九宫重排
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.037340 second(s), 10 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved