emmmm....

在被新生暴打后，我花了很久才补出这道DFS。由于WA1检查了半天，最后竟然是输出少了一个：   ，心态小崩。

这里普通的dfs算出的连通区域并不能直接当做最后的答案。所以需要类似模拟的DFS来处理。

代码如下：

#include
     
      using namespace std;int q[12][12];//用数组标记该位置是空地、食物、还是障碍。 int pd[12][12];//判断有没有走过 int maxx=0;//记录最大路径长度 int a,b,mb;//a，b记录起始坐标，mb记录目标长度 void dfs(int x,int y,int s){	if(s>maxx) maxx=s;	if(q[(x+a-1)%a][y]&&!pd[(x+a-1)%a][y])	{		pd[(x+a-1)%a][y]=1;		if(q[(x+a-1)%a][y]==1) dfs((x+a-1)%a,y,s+1);		else if(q[(x+a-1)%a][y]==2)dfs((x+a-1)%a,y,s);		pd[(x+a-1)%a][y]=0;	}	if(q[(x+a+1)%a][y]&&!pd[(x+a+1)%a][y])	{		pd[(x+a+1)%a][y]=1;		if(q[(x+a+1)%a][y]==1) dfs((x+a+1)%a,y,s+1);		else if(q[(x+a+1)%a][y]==2) dfs((x+a+1)%a,y,s);		pd[(x+a+1)%a][y]=0;	}	if(q[x][(y+b-1)%b]&&!pd[x][(y+b-1)%b]) 	{		pd[x][(y+b-1)%b]=1;		if(q[x][(y+b-1)%b]==1) dfs(x,(y+b-1)%b,s+1);		else if(q[x][(y+b-1)%b]==2) dfs(x,(y+b-1)%b,s);		pd[x][(y+b-1)%b]=0;	}	if(q[x][(y+b+1)%b]&&!pd[x][(y+b+1)%b]) 	{		pd[x][(y+b+1)%b]=1;		if(q[x][(y+b+1)%b]==1) dfs(x,(y+b+1)%b,s+1);		else if(q[x][(y+b+1)%b]==2) dfs(x,(y+b+1)%b,s);		pd[x][(y+b+1)%b]=0;	}}int main(){	int i,r,l,s,t,xx,yy,j;	char k;	cin>>t;	l=1;	while(t--)	{		maxx=0;		cin>>a>>b>>mb;		for(i=0;i
      
       >k;				if(k=='#') q[i][j]=0;				else if(k=='o') q[i][j]=2;				else if(k=='.') q[i][j]=1;				else if(k=='x')				{					xx=i;yy=j;q[xx][yy]=0;				}				pd[i][j]=0;			}		}		dfs(xx,yy,0);		if(maxx>=mb-1) cout<<"Case #"<
       
        <<": Fits perfectly!"<
       
      
     

　　其中、比较值得注意的地方有两个。一个是蛇的“空间传送”。如何处理从a[0][k]到a[long-1][k]位置的行动。另一个是最后的比较，因为他要求全部出洞。而最后判断成功时尾巴一定是在洞口。所以可以直接把出生位置看成一个障碍（但是仍然从这里开始dfs），把长度-1.   还要注意，走到食物上时，长度会增加1，可以等效成“位置变化，长度不变”，来继续讨论。（因为如果改变全局变量mb的值，就会对dfs产生影响）