题解 P2493 【[SDOI2011]贪食蛇】
[SDOI2011]贪食蛇
道理咱都懂嘛，这道题显然就是搜索。于是就有勇士直接交了DFS大模拟。
在这里就重点讲一下状态压缩。
- 首先是蛇形态的预处理。
- 首先是蛇的问题，确定一条蛇，就需要头，和上一个身体相对于这个身体的方位。显然只有4个方向，我们就拿二进制状态下两个位来记录一个方向。
- 又因为，头部是没有“上一个身体”这个概念的，所以他就记录身体的长度。
- 我们发现，身长是4~7的，恰好四个数，我们就把身长减4，并压如“蛇”的状态中。
- 具体先算出题目给出的蛇的初始状态
for(int i=3; i>0; i--) { int k=0; if(snake[i-1][0]+dx[0]==snake[i][0]&&snake[i-1][1]+dy[0]==snake[i][1])k=0; if(snake[i-1][0]+dx[1]==snake[i][0]&&snake[i-1][1]+dy[1]==snake[i][1])k=1; if(snake[i-1][0]+dx[2]==snake[i][0]&&snake[i-1][1]+dy[2]==snake[i][1])k=2; if(snake[i-1][0]+dx[3]==snake[i][0]&&snake[i-1][1]+dy[3]==snake[i][1])k=3; q[1]=q[1]<<2|k; } q[1]<<=2; - 对于每一次蛇的移动，我们要判断它是否咬到自己的身子。
int snake_move(int stat,int len,int k) {//蛇的状态，长度，移动方向。 int tmp=stat; len+=4; k^=1;//移动方向，和上一个身子相对于头的方向相反。 int x=dx[k],y=dy[k]; for(int i=2; i<len; i++) { x+=dx[tmp&3]; y+=dy[tmp&3]; tmp>>=2; if(!x&&!y)return -1; }//判断咬到自己。 return (stat<<2&((1<<(len+len-2))-1))|k; //stat<<2|k表示移动后，头直接增长的状态，因为如果没有吃到果子，身体不会变长。所以要加len限制。 } - 在这里，我们需要离散化状态，并记录下来。并分出11位二进制位保存状态。
- 对于普通的移动。
for(int k=0; k<4; k++) { int stat1=snake_move(stat0,len0,k); if(stat1>=0) { int s1=stat1<<2|len0; if(!number[s1])q[++r]=s1,number[s1]=r;//离散化记录。 s[l][k]=number[s1];//离散化后的状态l向k爬，得到的离散化后的状态。 } } - 吃到果子的同理。
for(int k=0; k<4; k++) { int stat1=snake_move(stat0,len0+1,k); if(stat1>=0) { if(len0<3) { int s1=stat1<<2|(len0+1); if(!number[s1])q[++r]=s1,number[s1]=r; fs[l][k]=number[s1]; } else fs[l][k]=0; } }
- 处理完蛇的形态之后，我们就要开始真正的搜索了。
- 先说一下需要记录的状态。
- 头的坐标：横纵共8位
- 蛇的形态：11位
- 食物状态：4位
- 耗费的时间：3位
int make_stat(int x,int y,int ss,int fs,int wt) { return (x<<22)|(y<<18)|(ss<<7)|(fs<<3)|wt; } void get_stat(int &x,int &y,int &ss,int &fs,int &wt,int val) { x=val>>22&0xf; y=val>>18&0xf; ss=val>>7&0x7ff; fs=val>>3&0xf; wt=val&7; }
- 那么，在BFS遍历队列的时候。
- 一般的转移：
for(int k=0; k<4; k++) { int x1=x0+dx[k],y1=y0+dy[k],stat1=s[stat0][k],fstat1=fstat0,wt1=abs(mp[x1][y1]-mp[x0][y0]); if(!mp[x1][y1])continue; if(fmp[x1][y1]&&(fstat1&1<<(fmp[x1][y1]-1))) { fstat1^=1<<(fmp[x1][y1]-1); stat1=fs[stat0][k]; } else stat1=s[stat0][k]; if(stat1>=0) { int s1=make_stat(x1,y1,stat1,fstat1,wt1); if(!(vst[s1>>3]&1<<wt1)) { vst[s1>>3]|=1<<wt1; q[++r]=s1; p[r]=l;//记录由谁转移，后要统计答案。 } } } - 特别的，因为是BFS，为保证记忆化复杂度所以时间必须严格非减，对于任意两格之间的转移时间，我们得一个一个单位的等。
if(wt0) { int s1=make_stat(x0,y0,stat0,fstat0,wt0-1); if(!(vst[s1>>3]&1<<(wt0-1))) { vst[s1>>3]|=1<<(wt0-1); q[++r]=s1; p[r]=l; } } - 边界条件:食物吃完了，而且到达了终点。
if(!fstat0&&!wt0) { ansl=l;//记录最终答案。 break; }有了最终答案和每一次操作是由谁转移的记录，就倒着扫一遍统计就行了。
- 一般的转移：
- 先说一下需要记录的状态。