本文共 2225 字，大约阅读时间需要 7 分钟。
题意：游戏采用N*N的棋盘，方格数为1~~N^2.其实玩家位置在1，每次投一次骰子，问最少需要几次可以到大N*N这个格子。其中格子中有蛇和梯子，在蛇头则降至蛇尾，在梯子底部则升至梯子首部。
分析：蛇和梯子占据哪些方格并不重要，只需要知道蛇和梯子的起始位置即可。
在走了若干步之后，对于一个特定的格子只有两种状态：
（1）：在走了这些步数后存在一种方案使得玩家的位置位于此格
（2）：不存在这样一种方案。
所以，只需要记住每次投骰子后玩家可能到达的位置，直到可以到达第N*N个方格处时停止扩展。
// I'm the Topcoder//C#include #include #include #include #include #include //C++#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include 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; //codeforcestypedef unsigned int ui;typedef unsigned long long ui64;#define MP make_pairtypedef vector VI;typedef pair 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 double DIS(T va, T vb) { return sqr(va.x - vb.x, va.y - vb.y); }template inline T INTEGER_LEN(T v) { int len = 1; while (v /= 10) ++len; return len; }template 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+10int 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为1int main(){ int D; int N,S,L; scanf("%d",&D); while(D--){ scanf("%d%d%d",&N,&S,&L); for(int i=0;i N*N) break; //试探能不能用蛇或者梯子 for(int m=0;m
转载于:https://www.cnblogs.com/lanjiangzhou/archive/2013/03/28/2987216.html
View Code