自动搬运

查看原文

来自洛谷，原作者为

	jerry3128 Astill System

搬运于2025-08-24 21:38:18，当前版本为作者最后更新于2020-05-19 16:08:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[SDOI2011]贪食蛇

道理咱都懂嘛，这道题显然就是搜索。于是就有勇士直接交了DFS大模拟。

在这里就重点讲一下状态压缩。

1. 首先是蛇形态的预处理。
   • 首先是蛇的问题，确定一条蛇，就需要头，和上一个身体相对于这个身体的方位。显然只有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;
   		}
   }
   

2. 处理完蛇的形态之后，我们就要开始真正的搜索了。
   • 先说一下需要记录的状态。
     • 头的坐标：横纵共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;
     }
     

有了最终答案和每一次操作是由谁转移的记录，就倒着扫一遍统计就行了。