双向广搜——POJ 1198

本文主要是介绍双向广搜——POJ 1198，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

对应POJ题目：点击打开链接

Description

Solitaire is a game played on a chessboard 8x8. The rows and columns of the chessboard are numbered from 1 to 8, from the top to the bottom and from left to right respectively. 

There are four identical pieces on the board. In one move it is allowed to: 

• 
  
• move a piece to an empty neighboring field (up, down, left or right), 
  
• jump over one neighboring piece to an empty field (up, down, left or right). 
  

There are 4 moves allowed for each piece in the configuration shown above. As an example let's consider a piece placed in the row 4, column 4. It can be moved one row up, two rows down, one column left or two columns right. 
Write a program that: 

• 
  
• reads two chessboard configurations from the standard input, 
  
• verifies whether the second one is reachable from the first one in at most 8 moves, 
  
• writes the result to the standard output. 
  

Input

Output

Sample Input

4 4 4 5 5 4 6 5
2 4 3 3 3 6 4 6

Sample Output

YES

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <cstring>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN=1000;
const int INF=1<<30;
typedef long long LL;
int go[4][2]={0,1,0,-1,1,0,-1,0};
set<LL>s0;
set<LL>s1;struct point
{int x[4],y[4],step;
}pb,pe;LL Get(point pt)
{LL h=0;for(int i=0; i<4; i++){h|=(1LL<<(pt.x[i]*8+pt.y[i]-1));}return h;
}bool cal(point pt, int u)
{for(int i=0; i<4; i++){if(i!=u && pt.x[i]==pt.x[u] && pt.y[i]==pt.y[u])return 1;}return 0;
}bool tex(int x,int y)
{if(x<0 || x>=8 || y<0 || y>=8) return 0;return 1;
}void bfs(point p, bool flag)
{queue<point>q;p.step=0;if(!flag) s0.insert(Get(p));else s1.insert(Get(p));q.push(p);point p1;while(!q.empty()){p=q.front();q.pop();if(p.step==4) continue;for(int i=0; i<4; i++){for(int j=0; j<4; j++){p1=p;p1.x[i]+=go[j][0];p1.y[i]+=go[j][1];p1.step++;if(!flag){if(tex(p1.x[i],p1.y[i]) && !s0.count(Get(p1))){if(!cal(p1,i)){s0.insert(Get(p1));q.push(p1);}else{p1.x[i]+=go[j][0];p1.y[i]+=go[j][1];if(tex(p1.x[i],p1.y[i]) && !s0.count(Get(p1)) && !cal(p1,i)){s0.insert(Get(p1));q.push(p1);}}}}else{if(tex(p1.x[i],p1.y[i]) && !s1.count(Get(p1))){if(!cal(p1,i)){LL h=Get(p1);if(s0.find(h)!=s0.end()){printf("YES\n"); return;}s1.insert(h);q.push(p1);}else{p1.x[i]+=go[j][0];p1.y[i]+=go[j][1];if(tex(p1.x[i],p1.y[i]) && !s1.count(Get(p1) && !cal(p1,i))){LL h=Get(p1);if(s0.find(h)!=s0.end()){printf("YES\n"); return;}s1.insert(h);q.push(p1);}}}}}}}if(flag) printf("NO\n");
}int main()
{//freopen("in.txt","r",stdin);int x,y;while(scanf("%d%d", &x,&y)==2){--x;--y;pb.x[0]=x; pb.y[0]=y;int i;for(i=1; i<4; i++) {scanf("%d%d", &x, &y);--x;--y;pb.x[i]=x; pb.y[i]=y;}for(i=0; i<4; i++) {scanf("%d%d", &x, &y);--x;--y;pe.x[i]=x; pe.y[i]=y;}if(Get(pb)==Get(pe)) {printf("YES\n"); continue;}bfs(pb, 0);bfs(pe, 1);s0.erase(s0.begin(), s0.end());s1.erase(s1.begin(), s1.end());}
}

这篇关于双向广搜——POJ 1198的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！