http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=505
题目大意,跳棋,8*8的棋盘,上有4个棋子,给你一个初始状态给你一个结束状态,问能不能在8步之内从初始状态走到结束状态。
一般的想法,直接暴力DFS,使用状态压缩,状态表偷懒使用set,用时2S
如果使用双向BFS,从开始节点和结束节点同时开始BFS,需要考虑一个细节问题。就是如果控制两端搜索的步数。即要求一个循环内,两个搜索的步数是相同的。
其实很简单,设定一个计数n,BFS每一层搜索时,如果有需要push到队列中的装态,就给计数器加1,然后下一层搜索时,pop出n个状态。最后AC,60MS,几乎是0S。
#include<cstdio>
#include<queue>
#include<set>
#include<string.h>
#include<algorithm>
using namespace std;
int map[9][9],a[9];
int dirx1[4]={0,0,1,-1};
int diry1[4]={1,-1,0,0};
int dirx2[4]={0,0,2,-2};
int diry2[4]={2,-2,0,0};
struct state
{
int pos,cnt;
};
bool check(int r,int c)
{
if(r<=8&&r>=1&&c<=8&&c>=1)
return true;
return false;
}
void getmap(int pos)
{
memset(map,0,sizeof(map));
while(pos)
{
int c=pos%10;
pos/=10;
int r=pos%10;
pos/=10;
map[r][c]=1;
}
}
int getpos()
{
int r=0;
for(int i=1;i<=8;++i)
for(int j=1;j<=8;++j)
if(map[i][j])
{
r=r*10+i;
r=r*10+j;
}
return r;
}
bool bfs(int start,int end)
{
set<int>close;
close.insert(start);
queue<state>q;
state o;
o.pos=start;
o.cnt=0;
q.push(o);
int x,y;
while(!q.empty())
{
state t=q.front();
q.pop();
getmap(t.pos);
++t.cnt;
for(int i=1;i<=8;++i)
{
for(int j=1;j<=8;++j)
{
if(map[i][j])
{
for(int d=0;d<4;++d)
{
x=i+dirx1[d];
y=j+diry1[d];
if(check(x,y)&&!map[x][y])
{
map[i][j]=0;
map[x][y]=1;
int pt=getpos();
if(close.find(pt)==close.end())
{
close.insert(pt);
if(pt==end)
return true;
if(t.cnt<8)
{
t.pos=pt;
q.push(t);
}
}
map[i][j]=1;
map[x][y]=0;
}
x=i+dirx2[d];
y=j+diry2[d];
if(check(x,y)&&!map[x][y]&&map[i+dirx1[d]][j+diry1[d]])
{
map[i][j]=0;
map[x][y]=1;
int pt=getpos();
if(close.find(pt)==close.end())
{
close.insert(pt);
if(pt==end)
return true;
if(t.cnt<8)
{
t.pos=pt;
q.push(t);
}
}
map[i][j]=1;
map[x][y]=0;
}
}
}
}
}
}
return false;
}
bool dbfs(int start,int end)
{
set<int>close1;
set<int>close2;
close1.insert(start);
close2.insert(end);
queue<state>q1;
queue<state>q2;
state t1;
t1.pos=start;
t1.cnt=0;
q1.push(t1);
t1.pos=end;
q2.push(t1);
int x,y;
int n1=0;
int m1=1;//计数器
int n2=0;
int m2=1;//计数器
while(!q1.empty()||!q2.empty())
{
n1=m1;
m1=0;
n2=m2;
m2=0;
while(n1--)//保证步数相同
//if(!q1.empty())
{
state t=q1.front();
q1.pop();
getmap(t.pos);
++t.cnt;
for(int i=1;i<=8;++i)
{
for(int j=1;j<=8;++j)
{
if(map[i][j])
{
for(int d=0;d<4;++d)
{
x=i+dirx1[d];
y=j+diry1[d];
if(check(x,y)&&!map[x][y])
{
map[i][j]=0;
map[x][y]=1;
int pt=getpos();
if(close2.find(pt)!=close2.end())
return true;
if(close1.find(pt)==close1.end())
{
close1.insert(pt);
if(pt==end)
return true;
if(t.cnt<4)
{
t.pos=pt;
q1.push(t);
++m1;
}
}
map[i][j]=1;
map[x][y]=0;
}
x=i+dirx2[d];
y=j+diry2[d];
if(check(x,y)&&!map[x][y]&&map[i+dirx1[d]][j+diry1[d]])
{
map[i][j]=0;
map[x][y]=1;
int pt=getpos();
if(close2.find(pt)!=close2.end())
return true;
if(close1.find(pt)==close1.end())
{
close1.insert(pt);
if(pt==end)
return true;
if(t.cnt<4)
{
t.pos=pt;
q1.push(t);
++m1;
}
}
map[i][j]=1;
map[x][y]=0;
}
}
}
}
}
}
while(n2--)//保证步数相同
//if(!q2.empty())
{
state t=q2.front();
q2.pop();
getmap(t.pos);
++t.cnt;
for(int i=1;i<=8;++i)
{
for(int j=1;j<=8;++j)
{
if(map[i][j])
{
for(int d=0;d<4;++d)
{
x=i+dirx1[d];
y=j+diry1[d];
if(check(x,y)&&!map[x][y])
{
map[i][j]=0;
map[x][y]=1;
int pt=getpos();
if(close1.find(pt)!=close1.end())
return true;
if(close2.find(pt)==close2.end())
{
close2.insert(pt);
if(pt==end)
return true;
if(t.cnt<4)
{
t.pos=pt;
q2.push(t);
++m2;
}
}
map[i][j]=1;
map[x][y]=0;
}
x=i+dirx2[d];
y=j+diry2[d];
if(check(x,y)&&!map[x][y]&&map[i+dirx1[d]][j+diry1[d]])
{
map[i][j]=0;
map[x][y]=1;
int pt=getpos();
if(close1.find(pt)!=close1.end())
return true;
if(close2.find(pt)==close2.end())
{
close2.insert(pt);
if(pt==end)
return true;
if(t.cnt<4)
{
t.pos=pt;
q2.push(t);
++m2;
}
}
map[i][j]=1;
map[x][y]=0;
}
}
}
}
}
}
}
return false;
}
int main()
{
freopen("e:\\zoj\\zoj_1505.txt","r",stdin);
while(scanf("%d %d %d %d %d %d %d %d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8])!=EOF)
{
memset(map,0,sizeof(map));
map[a[1]][a[2]]=1;
map[a[3]][a[4]]=1;
map[a[5]][a[6]]=1;
map[a[7]][a[8]]=1;
int start=getpos();
scanf("%d %d %d %d %d %d %d %d",&a[1],&a[2],&a[3],&a[4],&a[5],&a[6],&a[7],&a[8]);
memset(map,0,sizeof(map));
map[a[1]][a[2]]=1;
map[a[3]][a[4]]=1;
map[a[5]][a[6]]=1;
map[a[7]][a[8]]=1;
int end=getpos();
if(start==end)
{
printf("YES\n");
continue;
}
if(dbfs(start,end))
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
发表评论
-
图的割点tarjan---zoj_1119
2011-10-24 23:00 1233http://acm.zju.edu.cn/on ... -
静态treap+线段树---zoj_2112
2011-09-29 23:06 1708http://acm.zju.edu ... -
NIM博弈游戏,SG函数---zoj_3084,zoj_2083
2011-09-23 23:00 1317Nim游戏是两个人进行的游戏有如下规则: ... -
多重背包--zoj_2156
2011-09-14 11:10 864首先介绍经典的三种背包问题,0-1背包,完全 ... -
模式串匹配---KMP
2011-08-31 20:49 1278朴素的的模式串匹配算法通常要在向前移动文本指针 ... -
八数码问题(A*&&双向BFS)---zoj_1217
2011-08-30 22:13 1665题目地址:http://acm.zju.edu.cn/onli ... -
ac自动机以及它上面的DFA
2011-08-08 23:04 2479AC自动机(Aho-Corasick)主要用 ... -
二分图最大匹配(匈牙利算法)--zoj1516,1525,2223
2011-07-20 22:36 1188二分图G(E,V)将点集合V分成两个部分L,R ... -
网络最大流(EK)---zoj_1734
2011-07-19 16:34 2132网络最大流是图论中的一个典型问题,为了精确的定 ... -
trie和前缀检查---zoj_2876
2011-07-13 23:03 869trie树是一种多叉树,广泛用于字典检索。如 ... -
位图bitmap
2011-07-13 21:08 916bitmap是一种广泛使用的数据结构,主要用在 ... -
LAC和RMQ的转化---zoj_3195
2011-07-12 22:35 1074我擦。。纠结了好久啊,从SF到TLE,先总结2 ... -
LAC的tarjan(离线)算法---zoj_1141
2011-07-08 17:52 1660LCA就不解释了,这里主要再次复习一下LC ... -
笛卡尔树以及treap---zoj_2243
2011-07-07 15:52 2841zoj_2243笛卡 ... -
线段染色,矩形切割,离散化---zoj_2301,zoj_1128
2011-06-24 22:32 1367染色问题:在一维坐标轴上(最右端为M),有N ... -
线段树---zoj_1610
2011-06-22 21:06 746线段树是一种二叉树的拓展,在线段树每个节点中 ... -
快速排序(qsort)
2011-06-16 17:03 779快速排序是一种高效的非稳定排序,它的基本思路 ... -
斐波那契散列
2011-06-16 16:38 3074斐波那契散列法其实是一种特殊的乘法散列,先来看乘法 ... -
强连通分支(scc)---tarjan
2011-06-15 16:17 1285本文大量 ... -
单源最短路径SPFA---zoj3146
2011-06-09 15:25 941针对Bellman-Ford算法效率比较低 ...
相关推荐
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
降群法解魔方 哈哈师大 使用双向BFS搜素
TS_BFS_Graph_Explorer-源码.rar
code for bfs algorithm
a program to find Dfs and bfs
src=http___i0.hdslb.com_bfs_ar
bfsk系统仿真 bfsk系统仿真 bfsk系统仿真
采用共轭方向法中的BFS方法进行优化,程序中采用简单算例,并附有文档说明
深度优先遍历和广度优先遍历算法实现从定点开始的遍历序列。
depth first search algorithm
使用networkx的dfs,bfs动画 这是我的学生项目,其任务是学习如何在图形上可视化算法。 在这项工作中,我对DFS和BFS的工作进行了动画处理。 为了处理图形,我使用了networkx包以及matplotlib和celluloid包来创建一个...
比较DFS与BFS 简单的实现了,小地图范围的两种寻路算法原理的比较。 左键控制,可自动寻找路径,方便观察
java 数据结构 实现图的广度优先算法
本程序时BPSK的过程仿真,在加性高斯白噪声下的信号传输和接收
bfs ,dfs algoritm in TC
BFS_tree faoca[ f aofjaandbada
dfs-bfs-master 网上找到的 dfs和bfs演示
对bfs(广度优先遍历)和dfs(深度优先遍历)的详细解析,帮助人们理解广搜和深搜
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
pacman 吃豆人算法程序在人工智能课上的算法实现程序,内部涉及的算法实现则是有本人独立完成,这一部分总共包括了DFS、BFS、A、const-cost-search.zip