hdu1401“Solitaire“

hdu1401“Solitaire“

hdu1401"Solitaire"(双向广搜）

题意

有一个8X8的棋盘，上面有4个棋子，棋子可以上下左右移动。给定一个初始状态和一个目标状态，问能否在8步之内到达。

注意点（我的错误）

• 移动一步，棋子落到另一个棋子上是，才可以移动两步。（容易理解为即可以移动一步，也可以移动两步。）
• 棋子不区分顺序，所以需要按一定规则排序后才可以确定一个状态。

思路

• 使用8维数组vis*标记，进行查重。
• 有八个方向向量vex*。
• 伪双向广搜：并不是真的从两个初始一起搜索，分别从目标状态、初始状态使用bfs搜索4步，它们的标记有交集即返回true。
• bfs(出发状态start，搜索时标记sign，目标标记endsign):两次广搜，其实就是出发点不同，搜索时进行所作的标记不同，停止标记不同而已，可以归纳成一个bfs()使用两次。

代码：

#include<iostream>
using namespace std;
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<queue>
const int vex[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};//方向向量
char vis[8][8][8][8][8][8][8][8];
struct Chess//棋子
{int x, y;
};
struct Node//状态
{Chess ches[4];int step;
};
class cmp//谓词类：小于//装了个X,可以直接写cmp函数的
{
public:bool operator()(Chess c1, Chess c2){if(c1.x == c2.x)return c1.y < c2.y;elsereturn c1.x < c2.x;}
};
void sortNode(Node& node)//排序数据之后才是状态
{sort(node.ches, node.ches+4, cmp());//cmp()是一个匿名类！
}
bool movee(Node& next, int c, int v)//chess[c]向vex[v]移动一步
{next.ches[c].x += vex[v][0];next.ches[c].y += vex[v][1];if(next.ches[c].x < 1 || next.ches[c].x > 8 || next.ches[c].y < 1 || next.ches[c].y > 8){return false;//棋盘越界}for(int i = 0; i < 4; i++){if(i != c && next.ches[c].x == next.ches[i].x && next.ches[c].y == next.ches[i].y){return false;//重叠}}return true;
}
bool tGetNode(Node& next, Node& src, int c, int v)//根据参数尝试获取一个状态，成功返回true
{for(int i = 0; i < 4; i++){next.ches[i] = src.ches[i];}next.step = src.step + 1;//棋子移动，当不成功是可以在移动一步for(int i = 0; i < 2; i++){if(movee(next, c, v)){//成功sortNode(next);return true;}}return false;//移动失败
}
char& atVis(Chess ches[])//根据状态返回vis相应一个位置引用：不用每次都写8维数组。注意减去1
{return vis[ches[0].x-1][ches[0].y-1][ches[1].x-1][ches[1].y-1][ches[2].x-1][ches[2].y-1][ches[3].x-1][ches[3].y-1];
}
//保存开始状态，目标状态
Node beg, tar;//从start状态进行广搜，已经搜索的标记sign,遇到endsign就成功，返回true
bool bfs(Node& start, char sign, char endsign)
{Node node, next;queue<Node> q;q.push(start);atVis(start.ches) = sign;//标记while(!q.empty()){node = q.front();q.pop();if(node.step < 4){//还没到4步for(int c = 0; c < 4; c++)//棋子维度for(int v = 0; v < 4; v++){//方向维度if(tGetNode(next, node, c, v)){//存在该转移方法的一个状态if(atVis(next.ches) == 0){//未被搜索过atVis(next.ches) = sign;//标记q.push(next);}else if(atVis(next.ches) == endsign){//找到结束标志return true;}}}}}return false;
}int main()
{//freopen(&#", "r", stdin);while(~scanf("%d%d", &beg.ches[0].x, &beg.ches[0].y)){//每一个案例for(int i = 1; i < 4; i++)scanf("%d%d", &beg.ches[i].x, &beg.ches[i].y);sortNode(beg);beg.step = 0;for(int i = 0; i < 4; i++)scanf("%d%d", &tar.ches[i].x, &tar.ches[i].y);sortNode(tar);tar.step = 0;memset(vis, 0, sizeof(vis));//第一个bfs搜索后标记‘2’，作为第二个bfs的搜索目标（本质）//第一个bfs返回false(因为没有‘1’)if(bfs(tar,'2', '1') || bfs(beg, '1', '2'))printf("YESn");//第二个bfs返回了trueelseprintf("NOn");//第二个bfs返回了false}return 0;
}

说一个令人兴奋的错误思路

在一个二维空间上，有一个点，可以上下左右四个方向可以移动一步。给出一个初始点和一个终点，问在在n步之内能否到达。
对于这题，非常简单，一个状态只由一个 点决定（hdu1401是4个点）。vis*是一个2维数组。
注意到，一个点1x2维，四个点4x2=8维，所以！！！hdu1401在某种意义下可以看作给定两个点（两种状态），问在8维空间中 8步之内初始状态（初始点）能否到达给定终点状态？
而且，因为空间中没有障碍，可以根据曼哈顿距离直接使用贪心法！！不用暴力的bfs，岂不美滋滋？？！
事实上这是错的：

1. 四个棋子是无顺序的，需要排序。在8维空间图上看，相邻的两个结点（状态）它们之间的花费不一定比不相邻的小！即状态的扩散不是连续的。而曼哈顿距离只是空间距离的一种评估，所以不能作为hdu1401的贪心评估函数！也就不能根据这个写贪心法。不过，一个多点状态转化为更高维的单点状态这个思想还是挺有意思的。

突然想到的另一个点：

关于A*算法（bfs+贪心)，应该使用的是优先队列priority_queue.

//伪代码
bfsA(状态 star, 状态 tar, 标记 sign, 搜索目标标记 tarsign){q.push(star);atVis(star) = sign;while(!q.empty()){node = q.top();q.pop();for(遍历步长临近的点){if(tryGetNext(next, node)){//tryGetNext:尝试获取下一个状态，评估函数最优是优先级最高if 搜索成功 atVis(next) == tarsign退出，返回结果elseq.push(next); atVis(next) = sign;}}}
}