首页 > 搜索 > BFS搜索 > HDU 1430 魔板-BFS-[解题报告] C++
2013
12-10

HDU 1430 魔板-BFS-[解题报告] C++

魔板

问题描述 :

在魔方风靡全球之后不久,Rubik先生发明了它的简化版――魔板。魔板由8个同样大小的方块组成,每个方块颜色均不相同,可用数字1-8分别表示。任一时刻魔板的状态可用方块的颜色序列表示:从魔板的左上角开始,按顺时针方向依次写下各方块的颜色代号,所得到的数字序列即可表示此时魔板的状态。例如,序列(1,2,3,4,5,6,7,8)表示魔板状态为:

1 2 3 4
8 7 6 5

对于魔板,可施加三种不同的操作,具体操作方法如下:

A: 上下两行互换,如上图可变换为状态87654321
B: 每行同时循环右移一格,如上图可变换为41236785
C: 中间4个方块顺时针旋转一格,如上图可变换为17245368

给你魔板的初始状态与目标状态,请给出由初态到目态变换数最少的变换步骤,若有多种变换方案则取字典序最小的那种。

输入:

每组测试数据包括两行,分别代表魔板的初态与目态。

输出:

对每组测试数据输出满足题意的变换步骤。

样例输入:

12345678
17245368
12345678
82754631

样例输出:

C
AC

Problem – 1430

  跟八数码相似的一题搜索题。做法可以是双向BFS或者预处理从”12345678″开始可以到达的所有状态,然后等价转换过去直接回溯路径即可。

代码如下:

#include <cstdio>
 #include <iostream>
 #include <algorithm>
 #include <cstring>
 #include <map>
 #include <stack>
 #include <string>
 
 using namespace std;
 
 char q[44444][10], op[44444], tmp[10];
 int qh, qt, last[44444];
 map<string, int> pos;
 
 void op1(char *s) { reverse(s, s + 8);}
 
 void op2(char *s, bool op) {
     if (op) {
         rotate(s, s + 3, s + 4);
         rotate(s + 4, s + 5, s + 8);
     } else {
         rotate(s, s + 1, s + 4);
         rotate(s + 4, s + 7, s + 8);
     }
 }
 
 void op3(char *s, bool op) {
     char t;
     if (op) {
         t = s[1];
         s[1] = s[6];
         s[6] = s[5];
         s[5] = s[2];
         s[2] = t;
     } else {
         t = s[1];
         s[1] = s[2];
         s[2] = s[5];
         s[5] = s[6];
         s[6] = t;
     }
 }
 
 void PRE() {
     for (int i = 0; i < 8; i++) tmp[i] = i + '0';
     tmp[8] = 0;
     pos.clear();
     qh = qt = 0;
 
     strcpy(q[qt], tmp);
     pos[tmp] = qt;
     last[qt] = -1;
     op[qt++] = 0;
     while (qh < qt) {
         strcpy(tmp, q[qh]);
         op1(tmp);
         if (pos.find(tmp) == pos.end()) {
             strcpy(q[qt], tmp);
             pos[tmp] = qt;
             last[qt] = qh;
             op[qt++] = 'A';
         }
 
         strcpy(tmp, q[qh]);
         op2(tmp, true);
         if (pos.find(tmp) == pos.end()) {
             strcpy(q[qt], tmp);
             pos[tmp] = qt;
             last[qt] = qh;
             op[qt++] = 'B';
         }
 
         strcpy(tmp, q[qh]);
         op3(tmp, true);
         if (pos.find(tmp) == pos.end()) {
             strcpy(q[qt], tmp);
             pos[tmp] = qt;
             last[qt] = qh;
             op[qt++] = 'C';
         }
 
         qh++;
     }
 }
 
 int main() {
 //    freopen("in", "r", stdin);
     PRE();
     char bg[10], ed[10], con[10];
     while (cin >> bg >> ed) {
         for (int i = 0; i < 8; i++) {
             int t = 0;
             while (bg[i] != ed[t]) t++;
             con[t] = i + '0';
         }
         con[8] = 0;
         int cur = pos[con];
         stack<char> path;
         while (!path.empty()) path.pop();
         while (cur) {
             path.push(op[cur]);
             cur = last[cur];
         }
         while (!path.empty()) {
             putchar(path.top());
             path.pop();
         }
         puts("");
     }
     return 0;
 }

 

——written by Lyon

 

解题报告转自:http://www.cnblogs.com/LyonLys/p/hdu_1430_Lyon.html


,
  1. 可以参考算法导论中的时间戳。就是结束访问时间,最后结束的顶点肯定是入度为0的顶点,因为DFS要回溯

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。