【ZOJ2276】Lara Croft（bfs）---饶文津

题意

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; } ---来自腾讯云社区的---饶文津