Baudelaire is Programmer

1.Snail Trail

DFS，Snail的移动路线可以分为一个个线段，每个线段成为DFS的一个阶段，当Snail在一个方向上运动受阻时枚举转向的方向并进入下一阶段。开始时由于我重复搜索运动受阻时的点导致无限重复“撞墙”结果爆栈了，看来在写递归函数时还有很多细节需要注意。

/*
ID: huilong1
LANG: C++
TASK: snail
*/
#include<iostream>
#include<fstream>
#include<stdlib.h>
using namespace std;

ifstream fin;
ofstream fout;
int N,B;
char map[121][121];
int direct[4][2]={
	{0,1},{0,-1},{1,0},{-1,0}
};

int dfs(int x,int y){
	int maxlen=0;
	for(int k=0;k<4;k++){
		int len=0;
		int i,j;
		i=x;
		j=y;
		while(1){
			int nx,ny;
			nx=i+direct[k][0];
			ny=j+direct[k][1];
			if(nx>=N||nx<0||ny>=N||ny<0||map[nx][ny]=='#'){
				if(len==0)break;//防止重复“撞墙”造成的爆栈
				int futurlen=dfs(i,j);
				if(len+futurlen>maxlen)maxlen=futurlen+len;
				break;
			}
			if(map[nx][ny]=='-'){
				if(len>maxlen)maxlen=len;
				break;
			}
			i=nx;
			j=ny;
			map[i][j]='-';
			len++;
		}
		if(len==0)continue;//这句很重要，防止消除痕迹时形成死循环
		int ii=x+direct[k][0],jj=y+direct[k][1];
		//回溯，消除痕迹
		while(!(ii==i&&jj==j)){
			map[ii][jj]='.';
			ii+=direct[k][0];
			jj+=direct[k][1];
		}
		map[i][j]='.';
	}
	return maxlen;
}

int main(){
	fin.open("snail.in");
	fout.open("snail.out");
	fin>>N>>B;
	for(int i=0;i<N;i++)for(int j=0;j<N;j++)map[i][j]='.';
	for(int i=0;i<B;i++){
		char x;
		int y;
		fin>>x>>y;
		map[(int)(x-'A')][y-1]='#';
	}
	map[0][0]='-';
	fout<<dfs(0,0)+1<<endl;
	return 0;
}

2.Electric Fences

题目对精度要求不高，可以把平面坐标扩大10倍，这样就只需搜索0=<x<=1000和0<=y<=1000范围内的整点，但是搜索所有点还是会超时。首先试验了一下模拟退火算法（Simulated annealing），结果由于对“温度”和随机变化的过程把握不好，导致得到次优解并且波动很大，最终放弃并试了一个不太严谨的方法：先按步长为10搜索所有整点，找到其中的最优点，然后在最优点x和y方向上+-10的范围内提高精度按步长1搜索最优解。

3.Visconsin Square

时限是5秒，简单的DFS就可以过。

模拟退火（Simulated annealing）算法：

以下内容出自heaad的博客

/*
 *  J(y)：在状态y时的评价函数值
 *  Y(i)：表示当前状态
 *  Y(i+1)：表示新的状态
 *  r： 用于控制降温的快慢
 *  T： 系统的温度，系统初始应该要处于一个高温的状态
 *  T_min ：温度的下限，若温度T达到T_min，则停止搜索
*/
while( T > T_min )
{
　　dE = J( Y(i+1) ) - J( Y(i) ) ;  

　　if ( dE >= 0 )  //表达移动后得到更优解，则总是接受移动
        Y(i+1) = Y(i) ;  //接受从Y(i)到Y(i+1)的移动
　　else
　　{
    // 函数exp( dE/T )的取值范围是(0,1) ，dE/T越大，则exp( dE/T )也
        if ( exp( dE/T ) > random( 0 , 1 ) )
            Y(i+1) = Y(i) ;  //接受从Y(i)到Y(i+1)的移动
　　}
　　T = r * T ;  //降温退火 ，0<r<1 。r越大，降温越慢；r越小，降温越快
　　/*
　　* 若r过大，则搜索到全局最优解的可能会较高，但搜索的过程也就较长。若r过小，则搜索的过程会很快，但最终可能会达到一个局部最优值
　　*/
　　i ++ ;
}

四. 使用模拟退火算法解决旅行商问题