链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=555
题意：一个n*n格的棋盘，从1标号到n*n。从1开始走，每次投色子，可走1到6步中的任意一个步数，问最少投几次色子可到最后一格。其中有两种特殊通道，蛇和梯子，在蛇头所在的格子可以直接走到蛇尾所在的格子，在梯子底端所在的格子可以直接走到梯子顶端所在的格子。
思路：由于蛇和梯子作用是一样的，所以可以把它们看成一种。又由于蛇和梯子是不会重合的，所以它们不可能在同一个位置出现。故可以用barrier[x]数组来保存在特殊位置x处可以到达的位置y。grid[]数组来保存走的状态，-1表示不会走到，其它的数字表示最先可以到达该格子的投色子的次数。比如说某格子i在第一次投色子的过程中可以到达，标记为1，然后在对其他格子进行扩展的过程中，又可以到达格子i，此时不再更新grid[i],若果更新了的话，就会使所需要的投色子的次数变多。还有需要注意的是，格子的标号是从1开始的，一不小心就错了。
代码交上去一直re，不明所以，求大神指点。
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<string> #include<cmath> #include<algorithm> #include<map> using namespace std; const int maxn=25*25; int grid[maxn]; int barrier[maxn]; int main() { int d,n,s,l; int x,y,step; scanf("%d",&d); while(d--) { step=0; memset(grid,-1,sizeof(grid)); memset(barrier,0,sizeof(barrier)); scanf("%d%d%d",&n,&s,&l); for(int i=1;i<=s+l;i++)//从1开始的 { scanf("%d%d",&x,&y); barrier[x]=y; } grid[1]=0; while(grid[n*n]==-1) { for(int i=1;i<=n*n-1;i++) { if(grid[i]==step) { for(int j=1;j<=6;j++) { x=i+j; if(x>n*n) break; if(barrier[x]!=0) x=barrier[x]; if(grid[x]==-1)//避免重复 grid[x]=step+1; // cout<<x<<' '<<grid[x]<<endl; } } } step++; } printf("%d\n",step); } return 0; }