蓝桥杯 历届试题 九宫重排

  1. 云栖社区>
  2. 博客列表>
  3. 正文

蓝桥杯 历届试题 九宫重排

hjzgg 2016-04-28 16:25:29 浏览1175 评论0

摘要: 问题描述   如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。 我们把第一个图的局面记为:12345678. 把第二个图的局面记为:123.46758 显然是按从上到下,从左到右的顺序记录数字,空格记为句点。

问题描述
  如下面第一个图的九宫格中,放着 1~8 的数字卡片,还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动,可以形成第二个图所示的局面。

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

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#include<set> 
#define N 20005
using namespace std;

char mp[3][3], gp[3][3];
int dir[4][2] = {0,1, 1,0, -1,0, 0,-1};
char str[10];
struct node{
    int x, y;
    int step;
    char cur_mp[3][3];//记录当前图案
    node(){
    }
    node(int x, int y, int step){
        this->x = x;
        this->y = y;
        this->step = step;
    }
};
set<int>st;
queue<node>q;
bool check(node cur){
    for(int i=0; i<3; ++i)
        for(int j=0; j<3; ++j)
            if(cur.cur_mp[i][j] != gp[i][j])
                return false;
    return true;
}

int cal(node cur){//每一次移动将会映射到一个不同的整数
    int ss = 0;
    for(int i=0; i<3; ++i)
        for(int j=0; j<3; ++j)
            if(cur.cur_mp[i][j] != '.')
                ss = ss*10+(cur.cur_mp[i][j]-'0');
            else ss = ss*10+9;
    return ss;
}

void bfs(){
    st.clear();
    if(!q.empty())
        st.insert(cal(q.front()));
    while(!q.empty()){
        node cur = q.front();
        q.pop();
        if(check(cur)) {
            cout<<cur.step<<endl;
            return ;
        }
        
        for(int i=0; i<4; ++i){
            int xx = cur.x+dir[i][1];
            int yy = cur.y+dir[i][0];
            if(xx<0 || xx>2 || yy<0 || yy>2) continue;
            node nt = node(xx, yy, cur.step+1);
            memcpy(nt.cur_mp, cur.cur_mp, sizeof(cur.cur_mp));
            nt.cur_mp[cur.x][cur.y]^=nt.cur_mp[xx][yy];
            nt.cur_mp[xx][yy]^=nt.cur_mp[cur.x][cur.y];
            nt.cur_mp[cur.x][cur.y]^=nt.cur_mp[xx][yy];
            int val = cal(nt);
            if(st.find(val) != st.end()) continue;
            st.insert(val);
            q.push(nt);
        }
    }
    cout<<-1<<endl;
}

int main() {
    while(cin>>str){
        int bx, by;
        while(!q.empty()) q.pop();
        int len = 0;
        for(int i=0; i<3; ++i)
            for(int j=0; j<3; ++j){
                mp[i][j] = str[len++];
                if(mp[i][j] == '.') bx=i, by=j;
            }
        node cur = node(bx, by, 0);
        memcpy(cur.cur_mp, mp, sizeof(mp));
        q.push(cur);
        cin>>str;
        len = 0;
        for(int i=0; i<3; ++i)
            for(int j=0; j<3; ++j)
                gp[i][j] = str[len++];
        bfs();
    }
    return 0;
}

【云栖快讯】你想见的Java技术专家都在这了,向大佬提问,有问题必答  详情请点击

网友评论

hjzgg
文章323篇 | 关注12
关注
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
RDS是一种稳定可靠、可弹性伸缩的在线数据库服务。支持MySQL、SQL Server、Po... 查看详情
阿里云总监课正式启航

阿里云总监课正式启航