作者:UP7家族--婵婵_172 | 来源:互联网 | 2023-10-11 18:41
BFS-USACO-MagicSquares(魔板)Rubik先生在发明了风靡全球的魔方之后,又发明了它的二维版本——魔板。这是一张有8个大小相同的格子的魔板
BFS - USACO - Magic Squares(魔板) Rubik 先生在发明了风靡全球的魔方之后,又发明了它的二维版本——魔板。
这是一张有 8 个大小相同的格子的魔板:
1 2 3 4 8 7 6 5
我们知道魔板的每一个方格都有一种颜色。
这 8 种颜色用前 8 个正整数来表示。
可以用颜色的序列来表示一种魔板状态,规定从魔板的左上角开始,沿顺时针方向依次取出整数,构成一个颜色序列。
对于上图的魔板状态,我们用序列 (1,2,3,4,5,6,7,8) 来表示,这是基本状态。
这里提供三种基本操作,分别用大写字母 A,B,C 来表示(可以通过这些操作改变魔板的状态):
A:交换上下两行; B:将最右边的一列插入到最左边; C:魔板中央对的4个数作顺时针旋转。
下面是对基本状态进行操作的示范:
A:
8 7 6 5 1 2 3 4
B:
4 1 2 3 5 8 7 6
C:
1 7 2 4 8 6 3 5
对于每种可能的状态,这三种基本操作都可以使用。
你要编程计算用最少的基本操作完成基本状态到特殊状态的转换,输出基本操作序列。
**注意:**数据保证一定有解。
输入格式 输入仅一行,包括 8 个整数,用空格分开,表示目标状态。
输出格式 输出文件的第一行包括一个整数,表示最短操作序列的长度。
如果操作序列的长度大于0,则在第二行输出字典序最小的操作序列。
数据范围 输入数据中的所有数字均为 1 到 8 之间的整数。
输入样例:
2 6 8 4 5 7 3 1
输出样例:
7 BCABCCB
分析:
要求操作步数最少,字典序尽量小。要求操作步数最少,字典序尽量小。 要 求 操 作 步 数 最 少 , 字 典 序 尽 量 小 。
要字典序小,就按照A、B、C的顺序进行操作,用哈希表d存储每一种状态与初始状态之间的距离(操作次数),pre存储每一种状态是由哪一种状态转移而来的,是以何种操作转移而来的。要字典序小,就按照A、B、C的顺序进行操作,用哈希表d存储每一种状态与初始状态之间的距离(操作次数),\\pre存储每一种状态是由哪一种状态转移而来的,是以何种操作转移而来的。 要 字 典 序 小 , 就 按 照 A 、 B 、 C 的 顺 序 进 行 操 作 , 用 哈 希 表 d 存 储 每 一 种 状 态 与 初 始 状 态 之 间 的 距 离 ( 操 作 次 数 ) , p r e 存 储 每 一 种 状 态 是 由 哪 一 种 状 态 转 移 而 来 的 , 是 以 何 种 操 作 转 移 而 来 的 。
需要注意的是,本题是按照顺时针的顺序来表示状态的,为了与我们习惯一致,set函数来对第二列的数进行翻转操作。即将12345678转化为12348765。需要注意的是,本题是按照顺时针的顺序来表示状态的,为了与我们习惯一致,set函数来对第二列的数进行翻转操作。\\即将12345678转化为12348765。 需 要 注 意 的 是 , 本 题 是 按 照 顺 时 针 的 顺 序 来 表 示 状 态 的 , 为 了 与 我 们 习 惯 一 致 , s e t 函 数 来 对 第 二 列 的 数 进 行 翻 转 操 作 。 即 将 1 2 3 4 5 6 7 8 转 化 为 1 2 3 4 8 7 6 5 。
BFS求出最小步数后,再通过pre表反推具体操作。BFS求出最小步数后,再通过pre表反推具体操作。 B F S 求 出 最 小 步 数 后 , 再 通 过 p r e 表 反 推 具 体 操 作 。
代码:
#include #include #include #include #include using namespace std; const int N &#61; 1e6 ; string set ( string u) { string v; for ( int i&#61; 0 ; i< 4 ; i&#43;&#43; ) v&#43; &#61; u[ i] ; for ( int i&#61; 7 ; i>&#61; 4 ; i-- ) v&#43; &#61; u[ i] ; return v; } string A ( string t) { t&#61; set ( t) ; for ( int j&#61; 0 ; j< 4 ; j&#43;&#43; ) swap ( t[ j] , t[ j&#43; 4 ] ) ; return set ( t) ; } string B ( string t) { t&#61; set ( t) ; char u&#61; t[ 3 ] , v&#61; t[ 7 ] ; for ( int i&#61; 3 ; i>&#61; 1 ; i-- ) { t[ i] &#61; t[ i- 1 ] ; t[ i&#43; 4 ] &#61; t[ i&#43; 4 - 1 ] ; } t[ 0 ] &#61; u, t[ 4 ] &#61; v; return set ( t) ; } string C ( string t) { t&#61; set ( t) ; char u&#61; t[ 1 ] ; t[ 1 ] &#61; t[ 5 ] ; t[ 5 ] &#61; t[ 6 ] ; t[ 6 ] &#61; t[ 2 ] ; t[ 2 ] &#61; u; return set ( t) ; } string S&#61; "12345678" , E; string q[ N] ; unordered_map< string, int > d; unordered_map< string, pair< char , string>> pre; void bfs ( ) { int hh&#61; 0 , tt&#61; - 1 ; q[ &#43;&#43; tt] &#61; S; d[ S] &#61; 0 ; while ( hh<&#61; tt) { string t&#61; q[ hh&#43;&#43; ] ; if ( t&#61;&#61; E) return ; string u[ 3 ] ; u[ 0 ] &#61; A ( t) ; u[ 1 ] &#61; B ( t) ; u[ 2 ] &#61; C ( t) ; for ( int i&#61; 0 ; i< 3 ; i&#43;&#43; ) if ( ! d. count ( u[ i] ) ) { d[ u[ i] ] &#61; d[ t] &#43; 1 ; pre[ u[ i] ] &#61; { char ( &#39;A&#39; &#43; i) , t} ; q[ &#43;&#43; tt] &#61; u[ i] ; } } } int main ( ) { char c; for ( int i&#61; 0 ; i< 8 ; i&#43;&#43; ) { cin>> c; E&#43; &#61; c; } bfs ( ) ; int step&#61; d[ E] ; cout<< step<< endl; string ans; while ( E!&#61; S) { ans&#43; &#61; pre[ E] . first; E&#61; pre[ E] . second; } reverse ( ans. begin ( ) , ans. end ( ) ) ; if ( step) cout<< ans<< endl; return 0 ; }