题目链接：
https://vjudge.net/problem/UVALive-2554
题目大意：
题目的大概意思是又N*N的棋盘，编号从1 到 N*N 棋盘中分布着蛇和梯子玩家在位置1处，
然后掷骰子，如果点数在梯子尾则顺着梯子到达梯子头，若掷到蛇头，则滑到蛇尾
问最快到达终点所需掷的次数...
思路：
BFS跑一遍，但是这里的BFS存储的是每一步能到达的所有得状态，而且没有必要把每一步变成的状态存储下来，根据上一步就可以直接推下一步。比如下图，红色表示蛇，绿色表示梯子，下面列出了每一步能够到达的范围
第0步的时候
第1步的时候
第2步的时候
第3步的时候
所以可以用数组模拟每一步
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #include<queue> 7 #include<stack> 8 #include<map> 9 #include<set> 10 #include<sstream> 11 #include<functional> 12 using namespace std; 13 typedef long long ll; 14 const int maxn = 1000 + 10; 15 const int INF = 1e9 + 7; 16 int T, n, m, cases; 17 map<int, int>Map;//蛇和梯子的起点和终点 18 set<int>s; 19 int game[maxn];//保存游戏的每一步的状态 20 int cnt[maxn];//中间变量 21 int main() 22 { 23 cin >> T; 24 int m1, m2, x, y; 25 while(T--) 26 { 27 scanf("%d%d%d", &n, &m1, &m2); 28 Map.clear(); 29 s.clear(); 30 while(m1--) 31 { 32 cin >> x >> y; 33 Map[x] = y; 34 s.insert(x); 35 } 36 while(m2--) 37 { 38 cin >> x >> y; 39 Map[x] = y; 40 s.insert(x); 41 } 42 memset(game, 0,sizeof(game)); 43 memset(cnt, 0, sizeof(cnt)); 44 game[1] = 1; 45 int ans = 0;//记录步数 46 while(game[n * n] == 0) 47 { 48 memcpy(cnt, game, sizeof(game)); 49 memset(game, 0, sizeof(game)); 50 for(int i = 1; i < n * n; i++) 51 { 52 if(!cnt[i])continue;//为0表示此处没有到达 53 for(int k = 1; k <= 6; k++)//枚举骰子的点数 54 { 55 if(k + i > n * n)break;//已经出界 56 if(s.count(k + i))//如果此处是梯子或者蛇 57 { 58 game[Map[k + i]] = 1; 59 } 60 else game[k + i] = 1; 61 } 62 } 63 ans++; 64 } 65 cout<<ans<<endl; 66 } 67 return 0; 68 }
但是WA，而且这个链接根本没有人过了，强烈怀疑测试数据出错，百度了其他人的程序，都是大同小异。