题目链接：
https://vjudge.net/problem/UVALive-2554
题目大意：
题目的大概意思是又N*N的棋盘，编号从1 到 N*N 棋盘中分布着蛇和*玩家在位置1处，
然后掷骰子，如果点数在*尾则顺着*到达*头，若掷到蛇头，则滑到蛇尾
问最快到达终点所需掷的次数...
思路：
BFS跑一遍，但是这里的BFS存储的是每一步能到达的所有得状态，而且没有必要把每一步变成的状态存储下来，根据上一步就可以直接推下一步。比如下图，红色表示蛇，绿色表示*，下面列出了每一步能够到达的范围
第0步的时候
第1步的时候
第2步的时候
第3步的时候
所以可以用数组模拟每一步
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<sstream>
#include<functional>
using namespace std;
typedef long long ll;
const int maxn = + ;
const int INF = 1e9 + ;
int T, n, m, cases;
map<int, int>Map;//蛇和*的起点和终点
set<int>s;
int game[maxn];//保存游戏的每一步的状态
int cnt[maxn];//中间变量
int main()
{
cin >> T;
int m1, m2, x, y;
while(T--)
{
scanf("%d%d%d", &n, &m1, &m2);
Map.clear();
s.clear();
while(m1--)
{
cin >> x >> y;
Map[x] = y;
s.insert(x);
}
while(m2--)
{
cin >> x >> y;
Map[x] = y;
s.insert(x);
}
memset(game, ,sizeof(game));
memset(cnt, , sizeof(cnt));
game[] = ;
int ans = ;//记录步数
while(game[n * n] == )
{
memcpy(cnt, game, sizeof(game));
memset(game, , sizeof(game));
for(int i = ; i < n * n; i++)
{
if(!cnt[i])continue;//为0表示此处没有到达
for(int k = ; k <= ; k++)//枚举骰子的点数
{
if(k + i > n * n)break;//已经出界
if(s.count(k + i))//如果此处是*或者蛇
{
game[Map[k + i]] = ;
}
else game[k + i] = ;
}
}
ans++;
}
cout<<ans<<endl;
}
return ;
}
但是WA，而且这个链接根本没有人过了，强烈怀疑测试数据出错，百度了其他人的程序，都是大同小异。