蓝桥杯历届真题 九宫重排 康拓展开式

本文主要是介绍蓝桥杯历届真题 九宫重排 康拓展开式，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

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

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

输入格式

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

输出格式

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

样例输入

12345678.
123.46758

样例输出

3

样例输入

13524678.
46758123.

样例输出

22

#include <stdio.h>
#include <string.h>
#include <iostream>
#include<functional>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 4000005;
int f[maxn];
int xs[] = {-1,1,0,0};
int ys[] = {0,0,-1,1};
struct node
{char s[9];int step;
}mark[maxn];
void getf()  
{  f[0] = 0; f[1] = 1;  for( int i = 2; i <= 9; i ++ )  f[i] = f[i-1] * i;  
}  
int Cantor( char s[],int n )//n表示该排列有n个数  
{  int sum = 0;  for( int i = 0; i < n; i ++ )  {  int temp = 0;  for( int j = i + 1; j < n; j ++ )  if( s[j] < s[i] )  temp ++;  sum += f[n - i] * temp; //f[n]表示n的阶乘  }  return sum;  
} 
void BFS( node s,int e )
{queue<node>que;node cur,cnt;int tmp = Cantor( s.s,9 );mark[tmp] = s;que.push( s );while( !que.empty() ){cur = que.front(); que.pop();int z;for(  z = 0; z < 9; z ++ )	if( cur.s[z] == '0' )	break;int x = z/3,y = z%3;for( int i = 0; i < 4; i ++ ){int newx = x + xs[i];int newy = y + ys[i];int newz = newx*3 + newy;if( newx >= 0 && newx < 3 && newy >= 0 && newy < 3 ){cnt = cur;cnt.s[newz] = cur.s[z];cnt.s[z] = cur.s[newz];int k = Cantor( cnt.s,9 );if( k == e ){printf("%d\n",cur.step+1);return;}if( mark[k].step == 0 ){mark[k] = cnt;mark[k].step = cur.step + 1;que.push( mark[k] );}}}}
}
int main()
{#ifndef ONLINE_JUDGE  freopen("data.txt","r",stdin);  #endif 	getf();node s,e;for( int i = 0; i < 9; i ++ ){scanf("%ch",&s.s[i]);if( s.s[i] == '.' )	s.s[i] = '0';}getchar();for( int i = 0; i < 9; i ++ ){scanf("%ch",&e.s[i]);if( e.s[i] == '.' )	e.s[i] = '0';}s.step = 0;BFS( s,Cantor(e.s,9) );getchar();return 0;
}

这篇关于蓝桥杯历届真题 九宫重排 康拓展开式的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！