朴素搜索即刻, 注意终止条件和行走路线的模拟.
/**//*
ID: lorelei3
TASK: snail
LANG: C++
*/
#include <fstream>
#include <cmath>
#include <memory.h>
using namespace std;
const int MAXN = 125;
const int dx[] = 
{1, 0,-1, 0};
const int dy[] = {0, 1, 0,-1};
ifstream fin("snail.in");
ofstream fout("snail.out");
char board[MAXN][MAXN];
int n,b;
void input(){
memset(board, '.', sizeof(board));
fin>>n>>b;
for(int i=0; i<b; ++i){
fin.get();
char ch; int a;
fin>>ch>>a;
board[a][ch-'A'+1]='#';
}
}
int ans;
bool bound(int x, int y){
if(x<1 || x>n) return true;
if(y<1 || y>n) return true;
if(board[x][y]=='#') return true;
if(board[x][y]=='0') return true;
return false;
}
bool terminal(int x, int y, int dir){
if(board[x+dx[dir]][y+dy[dir]]=='0')
return true;
for(int i=0; i<4; ++i){
if(abs(i-dir)==2) continue;
int tx=x+dx[i];
int ty=y+dy[i];
if(tx<1||tx>n) continue;
if(ty<1||ty>n) continue;
if(board[tx][ty]=='.')
return false;
}
return true;
}
void dfs(int x, int y, int dir,int cnt){
if(terminal(x,y,dir)){
if(cnt>ans)
ans=cnt;
return;
}
else{
board[x][y]='0';
int tx=x+dx[dir];
int ty=y+dy[dir];
int dt;
if(bound(tx,ty)){
dt=dir+1>3?0:dir+1;
tx=x+dx[dt];
ty=y+dy[dt];
if(!bound(tx,ty))
dfs(tx, ty, dt, cnt+1);
dt=dir-1<0?3:dir-1;
tx=x+dx[dt];
ty=y+dy[dt];
if(!bound(tx,ty))
dfs(tx, ty, dt, cnt+1);
}else
dfs(tx, ty, dir, cnt+1);
board[x][y]='.';
}
}
void output(){
fout<<ans<<endl;
}
int main(){
input();
dfs(1,1,0,1);
dfs(1,1,1,1);
output();
return 0;
}posted on 2011-02-09 01:24
小阮 阅读(231)
评论(0) 编辑 收藏 引用 所属分类:
USACO