题意:http://acm.hdu.edu.cn/showproblem.php?pid=1401

给你8*8的棋盘和4个棋子初始位置、最终位置,问你能否在8次操作后达到该状态。

思路:

双向BFS,起点开始正搜4步,终点倒搜4步,map标记。

 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#include <cstdio>//sprintf islower isupper
#include <cstdlib>//malloc exit strcat itoa system("cls")
#include <iostream>//pair
#include <fstream>//freopen("C:\\Users\\13606\\Desktop\\Input.txt","r",stdin);
#include <bitset>
//#include <map>
#include<unordered_map>
#include <vector>
#include <stack>
#include <set>
#include <string.h>//strstr substr strcat
#include <string>
#include <time.h>// srand(((unsigned)time(NULL))); Seed n=rand()%10 - 0~9;
#include <cmath>
#include <deque>
#include <queue>//priority_queue<int, vector<int>, greater<int> > q;//less
#include <vector>//emplace_back
//#include <math.h>
#include <cassert>
#include <iomanip>
//#include <windows.h>//reverse(a,a+len);// ~ ! ~ ! floor
#include <algorithm>//sort + unique : sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)
using namespace std;//next_permutation(a+1,a+1+n);//prev_permutation
//******************
clock_t __START,__END;
double __TOTALTIME;
void _MS(){__START=clock();}
void _ME(){__END=clock();__TOTALTIME=(double)(__END-__START)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}
//***********************
#define rint register int
#define fo(a,b,c) for(rint a=b;a<=c;++a)
#define fr(a,b,c) for(rint a=b;a>=c;--a)
#define mem(a,b) memset(a,b,sizeof(a))
#define pr printf
#define sc scanf
#define ls rt<<1
#define rs rt<<1|1
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
const double E=2.718281828;
const double PI=acos(-1.0);
const ll INF=(1LL<<);
const int inf=(<<);
const double ESP=1e-;
const int mod=(int)1e9+;
const int N=(int)1e6+; int mp[][];
unordered_map<ull,bool>mark;
struct node
{
ull id;
int step;
};
ull get()
{
ull now=,temp=;
int cnt=-;
for(int i=;i<=;++i)
{
for(int j=;j<=;++j)
{
++cnt;
if(mp[i][j])
now|=temp<<cnt;
}
}
return now;
}
bool ok(int x,int y)
{
return x>=&&x<=&&y>=&&y<=;
}
bool ans;
void bfs(ull start,bool f)
{
queue<node>q;
q.push({start,});
while(!q.empty())
{
node now=q.front();q.pop();
if(!f)
{
if(mark[now.id])continue;
mark[now.id]=;
}
else
{
if(mark[now.id])
{
ans=;
return;
}
}
if(now.step==)continue;
int cnt=-;
for(int i=;i<=;++i)
{
for(int j=;j<=;++j)
{
++cnt;
mp[i][j]=(int)(now.id>>cnt)&;
}
}
for(int i=;i<=;++i)
{
for(int j=;j<=;++j)
{
if(mp[i][j]&&ok(i-,j)&&mp[i-][j]==&&ok(i-,j)&&mp[i-][j]==)
{
mp[i-][j]=,mp[i][j]=;
q.push({get(),now.step+});
mp[i-][j]=,mp[i][j]=;
}
if(mp[i][j]&&ok(i+,j)&&mp[i+][j]==&&ok(i+,j)&&mp[i+][j]==)
{
mp[i+][j]=,mp[i][j]=;
q.push({get(),now.step+});
mp[i+][j]=,mp[i][j]=;
}
if(mp[i][j]&&ok(i,j-)&&mp[i][j-]==&&ok(i,j-)&&mp[i][j-]==)
{
mp[i][j-]=,mp[i][j]=;
q.push({get(),now.step+});
mp[i][j-]=,mp[i][j]=;
}
if(mp[i][j]&&ok(i,j+)&&mp[i][j+]==&&ok(i,j+)&&mp[i][j+]==)
{
mp[i][j+]=,mp[i][j]=;
q.push({get(),now.step+});
mp[i][j+]=,mp[i][j]=;
}
//--------------------------------------------------------------
if(mp[i][j]==&&ok(i-,j)&&mp[i-][j]==)
{
mp[i-][j]=,mp[i][j]=;
q.push({get(),now.step+});
mp[i-][j]=;mp[i][j]=;
}
if(mp[i][j]==&&ok(i+,j)&&mp[i+][j]==)
{
mp[i+][j]=,mp[i][j]=;
q.push({get(),now.step+});
mp[i+][j]=;mp[i][j]=;
}
if(mp[i][j]==&&ok(i,j-)&&mp[i][j-]==)
{
mp[i][j-]=,mp[i][j]=;
q.push({get(),now.step+});
mp[i][j-]=;mp[i][j]=;
}
if(mp[i][j]==&&ok(i,j+)&&mp[i][j+]==)
{
mp[i][j+]=,mp[i][j]=;
q.push({get(),now.step+});
mp[i][j+]=;mp[i][j]=;
}
}
}
}
} int main()
{
int x,y;
while(~sc("%d%d",&x,&y))
{
ans=;
mark.clear();
mem(mp,);
mp[x][y]=;
for(int i=;i<=;++i)
{
sc("%d%d",&x,&y);
mp[x][y]=;
}
bfs(get(),);
mem(mp,);
for(int i=;i<=;++i)
{
sc("%d%d",&x,&y);
mp[x][y]=;
}
bfs(get(),);
if(ans)
pr("YES\n");
else
pr("NO\n");
}
return ;
} /**************************************************************************************/

最新文章

  1. log4j使用总结
  2. MySQL练习2
  3. 深入理解javascript原型和闭包(10)——this
  4. 微信小程序-上传下载
  5. Hibernate3 和Hibernate4 在配置文件上的区别
  6. 用canvas开发H5游戏小记
  7. 【英文版本】Android开源项目分类汇总
  8. Linux多线程之同步
  9. java web 学习四(http协议)
  10. AutoCAD 2014 win 32bit破解版
  11. 到底该不该熟悉掌握struts2的ONGL呢?
  12. Ubuntu下gcc及g++环境配置
  13. NGINX的CORS--跨域访问配置
  14. ios下点击穿透focus获取问题
  15. ubunru18.04下面安装docker
  16. JavaScript--图片放大镜
  17. 洛谷P1386座位安排
  18. RESTful API后台系统架构设计(Java)
  19. web程序的配置文件的修改
  20. Laravel中用GuzzleHttp

热门文章

  1. 8月清北学堂培训 Day 7
  2. 有向网络(带权的有向图)的最短路径Dijkstra算法
  3. 观察者模式在android网络监控下的运用
  4. mysql8.0.17gtid方式实现主从同步
  5. python线程+队列(queue)
  6. vim 永久显示行号 &amp; 临时显示行号
  7. Hive-概述
  8. linux内核中rtc框架选用什么接口来注册rtc设备呢?
  9. 008-网络抓包工具-wireshark
  10. mfc判断当前程序是否正在运行