概要： 一、问题分析 1.1 问题概况 1.2 可能难点
二、解决方法 2.1 构建模型 2.2 状态 2.3 搜索时的一些操作 2.4 代码
三、FAQ
一、 问题分析 1.1 问题概况 在大小不超过9*9的地图中，通过操作一条贪吃蛇，吃完所有食物并到达终点。地图中除贪吃蛇含有元素如下：
1） 老鼠：吃完后增加一长度。 2） 青蛙：吃完后增加一长度，并使蛇反向。 3） 大象：吃完后，每走一步不论是否吃怪都会增加一长度。 4） 螳螂：在被吃掉之前，蛇头不能正对螳螂。 5） 乌龟：吃掉后在原地留下一个乌龟壳，含有蛇头部分的尾部不能碰到乌龟壳。 6） 断蛇：有时蛇在初状态会断成两截，只能移动含蛇头的一截；含有蛇头部分的尾部碰到含有含有蛇尾部分的头部相邻时会自动接起。吃青蛙则蛇头蛇尾全盘互换；吃完所有食物后，蛇头碰到终点（不论是否已经连接）都会判作胜利。 7） 终点：必须吃完所有食物方能通过。未吃完所有食物前相当于墙。 1.2 难点分析 1）贪吃蛇的存储。 本人一开始想的是，每次移动相当于蛇头多了一截，吃或不吃的情况相当于蛇尾少了/没少。因此用1代表蛇头，3代表蛇尾，2代表蛇身进行移动。但很快就发现这种做法是不可行的。 因为，在很多情况下，我们蛇头移动一步以后马上就找不到新蛇尾了。这种局面有很多，“蛇自身盘旋”便是一种。 我最后采用的解法是，用1代表蛇头，其后包括蛇尾的每节蛇身，使用N，E，W，S中的一个字母存储，记录它的上一节蛇身（蛇头）在他的什么方位。找蛇尾的方法有两种：一种是全地图搜索是字母但周围一圈没有字母指向他的位子；一种是从蛇头开始DFS（深度优先搜索）。 2）翻转处理 接着上面的存储，在翻转时依然从蛇头开始DFS，寻找和他最近的字母并对应标好方向。紧接着的每一截后面的蛇都可以通过指向遍历到，新的方向显然正好与之前的相反(N变S，E变W)。到达蛇尾时，则发现没有可以继续遍历的蛇身了，于是重新记录蛇头。 3）断蛇处理（才不告诉你我还没玩到38关就写程序然后才发现有这茬…） 断蛇蛇头用2表示，其余和1一致。相接处理自不必言。 因为有断蛇，所以蛇尾一定要从蛇头开始DFS寻找。 在进行翻转的时候，先不能标记蛇头位置（否则一边标好以后地图上就把另外的蛇头顶掉了），等两边都处理好了以后，再在整个地图找1和2找回蛇头把蛇头标好。 二、 算法设计 2.1 算法 简单的DFS。其实使用BFS（宽度优先搜索）才能找到真正意义上的步数最少解，但主要是考虑到状态数可能会很多（写完以后，我发现36关找了14万个状态，50关找了85万个状态），因为状态里还要记录已经移动的步数，内存空间会爆炸。而众所周知很多时候会出现合法移动只有一步的情况，即使表面上步骤多也不一定是繁琐，因此我尝试了DFS。虽然找到的不是最优解，但程序消耗的时空会好一些。 解第50关时，也确实已经发现只有采用一开始随机化搜索方向的方法才有可能在5秒内出解（采用了劣的搜索顺序会导致运行时间超长）。因此此程序确实还有高人优化的空间。 2.2 状态记录 每一个场面(field)由以下部分组成。（建议配合代码阅读） 1） 场面情况。 蛇：1代表蛇头，2代表断蛇的后半段蛇头，蛇身用NEWS表示。 食物：螳螂用n/e/w/s其中的一个表示，其余a = 老鼠，b = 青蛙， c = 大象， d = 乌龟。 其他： 8代表墙壁，9代表终点。 2） 状态： ①当前吃了多少食物。(eat) ②是否吃到过大象。(ept) ③是否已经连接 ④两段蛇的蛇头/蛇尾位置。 ⑤当前走了哪些步，用于输出结果。 ⑥有哪些区域有乌龟壳。 2.3 搜索时的一些特技与细节 ①状态查重。哈希表存储遍历到哪些状态。每个状态乱搞一个哈希值（见代码）并使用cpp自带的set记录，如果已经遇到相同的hash值就扔掉这个状态。这是因为游戏关卡设计很容易导致搜索结果是我们的蛇一直在原地转圈圈。 ②只在开头钦定4个方向的搜索顺序。一开始想采用每找一个状态就随机一下搜索顺序的算法，事后发现由于许多关卡空地太大，这样做反而会拖慢程序，因为蛇绕圈的姿势更多了不好查重…. ③判螳螂一定需要在处理完程序以后再判，因为吃到青蛙马上转向是可以的。 2.4 代码
#include <bits/stdc++.h> #define MP make_pair #define FI first #define SE second #define LL long long using namespace std; const int N = 10; const int MAXSTEP = 400; int n,m,tot; const int dx[4] = {1,0,0,-1}; const int dy[4] = {0,1,-1,0}; const char lu[4] = {'S','E','W','N'}; const int mo = 1e9 + 9; set<int> st; int cont; inline int R(char c) { if (c == 'S') return 0; if (c == 'E') return 1; if (c == 'W') return 2; if (c == 'N') return 3; return -1; } inline int read() { int x = 0, f = 1; char ch = 0; for (;!isdigit(ch);ch =getchar()) if (ch == '-') f = -1; for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48; return x * f; } inline char readch() { char ch = 0; for (;!isgraph(ch); ch = getchar()); return ch; }//读入 struct field { char a[N][N];//地图 int eat,ept,con,tx,ty,wx,wy,tx2,ty2,wx2,wy2;//食物数量、吃过大象、是否连接、两段蛇的头尾 char step[MAXSTEP];//步数 bool dan[N][N];//有乌龟壳的格子 int cnt;//步数记录 }ori; bool avi(char ch,field k)//可以走的格子 { return (ch=='0'||islower(ch)||(k.eat>=tot&&ch=='9')); } inline void victory(field &u)//输出方案 { for (int i = 1; i <= u.cnt; ++i) { putchar(u.step[i]); if (!(i%5)) putchar(32); } exit(0); } bool vis[N][N]; inline void rever(field &u,int x,int y,int s) //将蛇反向 { bool pd = 0; vis[x][y] = 1; for (int i = 0; i < 4; ++i) { int xx = x + dx[i], yy = y + dy[i]; if (R(u.a[xx][yy] != -1) && R(u.a[xx][yy]) + i == 3 &&!vis[xx][yy]) { pd = 1; u.a[x][y] = lu[i];//蛇身反向 rever(u,xx,yy,s); } } if (!pd) { u.a[x][y] = s+48; if (u.con)u.tx = x, u.ty = y; //蛇是连接的没有关系，蛇如果不连接，一定要做两遍在重新找蛇头 } } inline pair<int,int> Wei1(field &u,int x,int y) //找蛇尾。一开始的x,y一定要是蛇头。 { bool pd = 0; vis[x][y] = 1; for (int i = 0; i < 4; ++i) { int xx = x + dx[i], yy = y + dy[i]; if (R(u.a[xx][yy] != -1) && R(u.a[xx][yy]) + i == 3 &&!vis[xx][yy]) { pd = 1; return Wei1(u,xx,yy); } } if (!pd) return MP(x,y); } inline int cnthash(field &u)//算一个哈希值代表这个状态来判重。 { int res = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) res = (1LL * res * 17 %mo + (int)u.a[i][j] * 37+ (int)u.dan[i][j]) % mo; res = (1LL * res * 23 %mo + (int)u.ept * 21 + (int)u.eat * 29 + (int) u.con * 31) %mo; return res; } int id[4]; inline void solve(field &u)//主程序 { int kl = cnthash(u); if (st.find(kl) != st.end()) return; st.insert(kl);//判重 for (int i1 = 0; i1 < 4; ++i1) { int i = id[i1]; int xx = u.tx + dx[i], yy = u.ty + dy[i]; if (xx < 0 || xx >= n || yy < 0 || yy >=m) continue;//蛇头超出边界 if (avi(u.a[xx][yy],u))//合法的移动 { if (u.a[xx][yy] == '9') u.step[++u.cnt] = lu[i],victory(u);//得到方案 field now = u; bool pd = 0; if (now.a[xx][yy] != '0') pd = 1;//吃到了食物 now.a[now.tx][now.ty] = lu[i]; now.tx = xx; now.ty = yy; char z = now.a[xx][yy]; now.a[xx][yy] = '1';//更新蛇头 if (pd || now.ept)//蛇尾不变的情况 { if (pd) now.eat ++; if (z == 'b') //两种不同情况下蛇的翻转。 { if (now.con)memset(vis,0,sizeof(vis)),rever(now,now.tx,now.ty,1); else { memset(vis,0,sizeof(vis)),rever(now,now.tx2,now.ty2,1); memset(vis,0,sizeof(vis)),rever(now,now.tx,now.ty,2); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (now.a[i][j]=='1') now.tx = i, now.ty = j; else if (now.a[i][j] == '2') now.tx2 = i,now.ty2 = j; } } else if (z == 'c') now.ept = 1;//吃到了大象 else if (z == 'd') now.dan[xx][yy] = 1;//吃到了乌龟壳 } else//没有吃到食物，蛇尾缩短 { memset(vis,0,sizeof(vis));pair<int,int> tail = Wei1(now,now.tx,now.ty); now.a[tail.FI][tail.SE] = '0'; } memset(vis,0,sizeof(vis)); pair<int,int> tail = Wei1(now,now.tx2,now.ty2); now.wx2 = tail.FI, now.wy2 = tail.SE; memset(vis,0,sizeof(vis)); tail = Wei1(now,now.tx,now.ty); now.wx = tail.FI, now.wy = tail.SE; //更新蛇尾 xx = now.tx, yy = now.ty; if (now.a[xx+1][yy] == 'n'|| now.a[xx-1][yy]=='s'||now.a[xx][yy-1] == 'e'||now.a[xx][yy+1]=='w') continue; //螳螂和乌龟一定要在后面判断，因为青蛙会反向。。 if (!now.con) for (int j = 0; j < 4; ++j) if (now.wx + dx[j] == now.tx2 && now.wy +dy[j] == now.ty2) { now.con = 1; now.wx = now.wx2, now.wy = now.wy2; now.a[now.tx2][now.ty2] = lu[3-j]; } //相接判断。 注意lu[j]和lu[3-j]刚好是相反方向。 if (now.dan[now.wx][now.wy]) continue; //乌龟 now.step[++now.cnt] = lu[i]; solve(now); } } } int main() { srand(time(NULL)); st.clear(); n = read();m = read(); for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) ori.a[i][j] = readch(); ori.eat = ori.ept = 0; ori.con = 1; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (ori.a[i][j]=='1') ori.tx = i, ori.ty = j; else if (ori.a[i][j] == '2') ori.con = 0,ori.tx2 = i,ori.ty2 = j; else if (islower(ori.a[i][j])) tot++; pair<int,int> tail = Wei1(ori,ori.tx,ori.ty); ori.wx = tail.FI, ori.wy = tail.SE; tail = Wei1(ori,ori.tx2,ori.ty2); ori.wx2 = tail.FI, ori.wy2 = tail.SE; //初状态读入及预处理 for (int i = 0; i < 4; ++i) id[i] = i; id[0] = 1; id[1] = 3; id[2] = 0; id[3] = 2;//实验发现这个搜索顺序可以让50关在4秒之内出解，否则会很慢（这就是为什么不用BFS..） solve(ori); return 0;//其实正常情况用不到return 0，因为一般是victory那里exit(0) }视频链接：https://www.bilibili.com/video/BV1L4411F76t
