记录编号	81495	评测结果	AAAAAAAAAAAA
题目名称	蜗牛的旅行	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2013-11-14 15:13:32	内存使用	0.34 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<vector>
#include<cstring>
#include<iomanip>
using namespace std;
const int SIZEN=123;
int board[SIZEN][SIZEN]={0};//0为空地,-1为路障,1为路径
int n;
int b;
int dx[]={0,0,0,1,-1};
int dy[]={0,1,-1,0,0};
int ans=0;
void print(void){
	for(int i=0;i<=n+1;i++){
		for(int j=0;j<=n+1;j++){
			if(board[i][j]==0) cout<<".";
			else if(board[i][j]==-1) cout<<"#";
			else if(board[i][j]==1) cout<<"s";
		}
		cout<<endl;
	}
}
bool canmove(int x,int y,int dir){
	return board[x+dx[dir]][y+dy[dir]]==0;
}
void eraselocus(int x,int y,int dir,int len){//擦去从x,y开始长度为len的路径,x,y这一点并不擦去
	int i;
	for(i=1;i<=len;i++){
		x+=dx[dir];
		y+=dy[dir];
		board[x][y]=0;
	}
}
int trylocus(int x,int y,int dir){//取得从x,y开始的最长长度,并将此路径标记为1(x,y这一点并不标记)
	int tot=0;
	while(canmove(x,y,dir)){
		tot++;
		x+=dx[dir];
		y+=dy[dir];
		board[x][y]=1;
	}
	return tot;
}
void DFS(int x,int y,int nowsum){
	int dir;
	int nextl;
	ans=max(ans,nowsum);
	int nx,ny;
	for(dir=1;dir<=4;dir++){
		if(canmove(x,y,dir)){
			nextl=trylocus(x,y,dir);
			nx=x+nextl*dx[dir],ny=y+nextl*dy[dir];
			if(board[nx+dx[dir]][ny+dy[dir]]==1){
				ans=max(ans,nowsum+nextl);
				eraselocus(x,y,dir,nextl);
			}
			else{
				DFS(nx,ny,nowsum+nextl);
				eraselocus(x,y,dir,nextl);
			}
		}
	}
}
void markborder(void){
	int i;
	for(i=1;i<=n;i++) board[0][i]=board[n+1][i]=board[i][0]=board[i][n+1]=-1;
}
void marklock(string str){
	int x,y;//x是行y是列
	y=str[0]-'A'+1;
	x=0;
	int i;
	for(i=1;i<str.size();i++){
		x*=10;
		x+=str[i]-'0';
	}
	board[x][y]=-1;
}
void work(void){
	board[1][1]=1;
	DFS(1,1,1);
	printf("%d\n",ans);
}
void read(void){
	scanf("%d%d",&n,&b);
	int i;
	string str;
	for(i=1;i<=b;i++){
		cin>>str;
		marklock(str);
	}
}
int main(){
	freopen("snail.in","r",stdin);
	freopen("snail.out","w",stdout);
	read();
	markborder();
	work();
	return 0;
}