题意：游戏采用N*N的棋盘，方格数为1~~N^2.其实玩家位置在1，每次投一次骰子，问最少需要几次可以到大N*N这个格子。其中格子中有蛇和梯子，在蛇头则降至蛇尾，在梯子底部则升至梯子首部。
分析：蛇和梯子占据哪些方格并不重要，只需要知道蛇和梯子的起始位置即可。
在走了若干步之后，对于一个特定的格子只有两种状态：
（1）：在走了这些步数后存在一种方案使得玩家的位置位于此格
（2）：不存在这样一种方案。
所以，只需要记住每次投骰子后玩家可能到达的位置，直到可以到达第N*N个方格处时停止扩展。
View Code
// I'm the Topcoder //C #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <math.h> #include <time.h> //C++ #include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <cctype> #include <stack> #include <string> #include <list> #include <queue> #include <map> #include <vector> #include <deque> #include <set> using namespace std; //*************************OUTPUT************************* #ifdef WIN32 #define INT64 "%I64d" #define UINT64 "%I64u" #else #define INT64 "%lld" #define UINT64 "%llu" #endif //**************************CONSTANT*********************** #define INF 0x3f3f3f3f #define eps 1e-8 #define PI acos(-1.) #define PI2 asin (1.); typedef long long LL; //typedef __int64 LL; //codeforces typedef unsigned int ui; typedef unsigned long long ui64; #define MP make_pair typedef vector<int> VI; typedef pair<int, int> PII; #define pb push_back #define mp make_pair //***************************SENTENCE************************ #define CL(a,b) memset (a, b, sizeof (a)) #define sqr(a,b) sqrt ((double)(a)*(a) + (double)(b)*(b)) #define sqr3(a,b,c) sqrt((double)(a)*(a) + (double)(b)*(b) + (double)(c)*(c)) //****************************FUNCTION************************ template <typename T> double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); } template <class T> inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; } template <typename T> inline T square(T va, T vb) { return va * va + vb * vb; } // aply for the memory of the stack //#pragma comment (linker, "/STACK:1024000000,1024000000") //end #define nmax 20+10 #define slmax 200+10 int grid[nmax*nmax+1];//棋盘(序号从1开始) int gridbak[nmax*nmax+1];//备份上一次棋盘状态 struct SnakeAndLadder{ int from; int to; }; SnakeAndLadder obstacle[2*slmax];//障碍物，包括梯子和蛇 int step;//投骰子的数目 int deal;//如果落脚处是蛇（惩罚）首部或者是梯子（奖励）底部，则deal为1 int main(){ int D; int N,S,L; scanf("%d",&D); while(D--){ scanf("%d%d%d",&N,&S,&L); for(int i=0;i<S+L;i++){ scanf("%d%d",&obstacle[i].from,&obstacle[i].to); } memset(grid,0,sizeof(grid)); grid[1]=1; step=0; while(grid[N*N]==0){ memcpy(gridbak,grid,sizeof(grid));//备份上一步棋盘的状态 memset(grid,0,sizeof(grid)); //搜索所有的格子，最后一格不用搜索，因为在搜索过程结束前它一定为0 for(int j=1;j<=N*N-1;j++){ if(gridbak[j]==0)//上一步无法到达此格，则跳过 continue; //考虑点数1~6，走改点数步数后到达j+k位置 for(int k=1;k<=6;k++){ deal=0; if(j+k>N*N) break; //试探能不能用蛇或者梯子 for(int m=0;m<S+L;m++){ //如果j+k位置是某个蛇或者梯子的起始位置 //则沿着它到达终止位置 if(obstacle[m].from==j+k){ grid[obstacle[m].to]=1; deal=1; break;//j+k位置至多只有一个蛇或者梯子的起止位置 } } //不用蛇或者梯子 if(deal==0&&grid[j+k]==0) grid[j+k]=1; } } step++; } printf("%d\n",step); } return 0; }