本文主要是介绍HDU 1401 Solitaire(双向搜索)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：LINK
题意： 在一个8×8的棋盘中，给定你4个棋子A，再给你4个棋子B，问你在8步之内能不能够从A位置移动到B位置；
规则：棋子能能上下左右移动，同时能跳过相邻的棋子到达相邻棋子的空地方；
如果直接搜索无论是bfs还是dfs都会TLE的，可以发现无论是从开始的棋盘搜索到最终的棋盘，还是从最终的棋盘搜索到开始的棋盘是一样的。
所以我们从开始的棋盘搜索4步，从最终的棋盘搜索4步，检测有没有相同的可以达到的状态。
我是用DFS写的，分别从初始态和最终态搜索，复杂度2*(16^4) ,为了记录是否可以到达某个棋盘，可以状态压缩4个点的坐标，一个8个数字，每个数字大小1~8(占3位),一共用24位.
当然也可以用BFS写。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
#define INF 1000000000
int mm[9][9];
bool vis[1<<24];
int flag ;
const int n = 8,m = 8;
struct node
{pair<int, int > p[6];
};
int dir[4][2]= { 0, 1, 0, -1, 1, 0, -1, 0};
node S, T;
pair<int, int> test(pair<int, int> in, int adx, int ady)
{pair<int, int> ret;int nx = in.first + adx;int ny = in.second + ady;if(nx < 1 || nx > n || ny < 1 || ny > m) {ret.first = ret.second = -1;return ret;}if(mm[nx][ny] != 1) {ret.first = nx; ret.second = ny;return ret;}nx += adx;ny += ady;if(nx < 1 || nx > n || ny < 1 || ny > m) {ret.first = -1; ret.second = -1;return ret;}if(mm[nx][ny] != 1) {ret.first = nx; ret.second = ny;return ret;}ret.first = ret.second = -1;return ret;
}
int getsta(node in)
{int sta = 0;int xx , yy;for(int i = 1; i<=4; i++) {xx = in.p[i].first;yy = in.p[i].second;xx --; yy --;sta = (sta << 3) | xx;sta = (sta << 3) | yy;}return sta;
}
void dfs(int x, node now, int ff)
{if(flag) return ;node next = now;sort(next.p+1, next.p+5);int sta = getsta(next);if(!ff) vis[sta] = 1;else if(vis[sta]) {flag = 1; return ;}if(x > 4) return ;memset(mm, 0, sizeof(mm));for(int i=1; i<=4; i++) mm[now.p[i].first][now.p[i].second] = 1;for(int i=1; i<=4; i++) {for(int j = 0; j< 4; j++) {next = now;pair<int, int> tmp = test(now.p[i], dir[j][0], dir[j][1]);if(tmp.first == -1) continue;next.p[i] = tmp;dfs(x+1, next, ff);}}
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGEint tmp;while(scanf("%d", &tmp) != EOF) {S.p[1].first = tmp;scanf("%d", &S.p[1].second);for(int i=2; i<=4; i++) scanf("%d%d", &S.p[i].first, &S.p[i].second);for(int i=1; i<=4; i++) scanf("%d%d", &T.p[i].first, &T.p[i].second);memset(vis, 0,sizeof(vis));sort(S.p+1, S.p+1+4);sort(T.p+1, T.p+1+4);flag = 0;dfs(1, S, 0);dfs(1, T, 1);if(flag) printf("YES\n");else printf("NO\n");}return 0;
}
这篇关于HDU 1401 Solitaire(双向搜索)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
