【ZOJ2276】Lara Croft(bfs)
BFS
2023-09-11 14:19:24 时间
BUPT2017 wintertraining(16) #4 D
ZOJ - 2276
题意
n个数字绕成环,有两个指示数字的方块,每次可以顺时针或逆时针移动其中一个,步数是它当前位置的数字a[i],给定它们的初始位置,求最少几步可使两个方块停在一个位置上的,或永远不可能。
题解
bfs,两个方块当前位置为状态。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#define N 105
using namespace std;
struct node{
int p,q,k;
};
int n,a[N],p,q,vis[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int bfs(){
queue<node>que;
memset(vis,0,sizeof vis);
que.push((node){p,q,0});
while(!que.empty()){
node k=que.front();
que.pop();
for(int i=0;i<4;i++){
int np=(k.p+a[k.p]*dx[i]+n)%n,nq=(k.q+a[k.q]*dy[i]+n)%n;
if(np==nq)return k.k+1;
if(!vis[np][nq]){
que.push((node){np,nq,k.k+1});
vis[np][nq]=1;
}
}
}
return -1;
}
int main() {
while(scanf("%d",&n),n){
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
scanf("%d%d",&p,&q);
int ans=bfs();
if(ans==-1)puts("Lara is traped!");
else printf("open it on the %dth move!\n",ans);
}
return 0;
}
相关文章
- 穿越雷区--蓝桥杯--DFS/BFS
- F: Horse Pro 马走棋盘 BFS
- hdu1548 A strange lift(bfs 或Dijkstra最短路径)
- Java实现 LeetCode 773 滑动谜题(BFS)
- Leetcode1926. 迷宫中离入口最近的出口(medium,BFS)
- Leetcode0429. N 叉树的层序遍历(medium, BFS)
- Leetcode969: 煎饼排序(medium, BFS)
- bfs——练习demo4(20届周新杰提供)
- POJ 3126-Prime Path(BFS)
- 迷宫3---BFS
- 用BFS解决迷宫问题
- C. Robot(BFS)
- PAT 1076 Forwards on Weibo[BFS][一般]
- golang BFS DFS
- 二叉树专题01------树的基础知识,遍历方式、前序遍历、中序遍历和后序遍历、递归、迭代、DFS、BFS、层序遍历