记录编号	195401	评测结果	AAAAAAAAAAAA
题目名称	蜗牛的旅行	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.012 s
提交时间	2015-10-18 20:09:47	内存使用	0.60 MiB

#include<cstdio>
#include<iostream>
#include<deque>
using namespace std;
const int SIZEN=200,INF=0x7fffffff/2;
int N,M;
int mp[SIZEN][SIZEN]={0};
int f[SIZEN][SIZEN],dx[]={0,0,1,-1},dy[]={1,-1,0,0},ans=0;
bool inq[SIZEN][SIZEN];
int get(char a)
{
	if('A'<=a&&a<='Z') return a-'A'+1;
	else cout<<"fuck"<<endl;
	return 0;
}
void read()
{
	scanf("%d%d",&N,&M);
	char a;
	int x,y;
	for(int i=1;i<=M;i++)
	{
		cin>>a;
		scanf("%d",&y);
		x=get(a);
		mp[y][x]=2;
	}
	for(int i=0;i<=N;i++) mp[i][0]=mp[0][i]=mp[N+1][i]=mp[i][N+1]=2;
}
bool pan(int x,int y)
{
	if(x==0||y==0||x>N||y>N) return 0;
	if(mp[x][y]) return 0;
	return 1;
}
void make(int x,int y,int len,int i)
{
	mp[x][y]=1;
	while(len)
	{
		x+=dx[i];y+=dy[i];
		len--;
		mp[x][y]=1;
	}
}
void erase(int x,int y,int len,int i)
{
	mp[x][y]=0;
	while(len)
	{
		x+=dx[i];y+=dy[i];
		len--;
		mp[x][y]=0;
	}
}
int getlong(int x,int y,int i)
{
	int ans=0;
	while(pan(x+dx[i],y+dy[i]))
	{
		x+=dx[i];y+=dy[i];
		ans++;
	}
	return ans;
}
void dfs(int x,int y,int nowsum)
{
	ans=max(ans,nowsum);
	//cout<<x<<" "<<y<<endl;
	for(int i=0;i<4;i++)
	{
		int nx=x,ny=y;
		int len=getlong(x,y,i);
		if(len==0) continue;
		nx+=len*dx[i],ny+=len*dy[i];
		make(x,y,len,i);
		if(mp[nx+dx[i]][ny+dy[i]]==1)
		{
			ans=max(ans,nowsum+len);
			erase(x,y,len,i);
		}
		else 
		{
			dfs(nx,ny,nowsum+len);
			erase(x,y,len,i);
		}
	}
}
void work()
{
	mp[1][1]=1;
	dfs(1,1,1);
	printf("%d",ans);
}
int main()
{
	freopen("snail.in","r",stdin);
	freopen("snail.out","w",stdout);
	read();
	work();
	return 0;
}