usaco_5_2_1_snail.cpp

usaco自己做的1到5章的代码

/*
PROB: snail
LANG: C++
*/
/*
这道题，不想说什么，直接搜索就是……一个深搜就可以~~
至于我那五次提交……唉！vis判定不是1，不要判定是0……
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<cstring>
#include<algorithm>
#define cin fin
#define MAXP 122
using namespace std;
char map[MAXP][MAXP],bat[5];
bool vis[MAXP][MAXP];
char maxmap[MAXP][MAXP];
int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,bn,maxn,step=0;
void is_max()
{
 if(step>maxn){
   maxn=step;
   memcpy(maxmap,map,sizeof(map));
 }
}
void dfs(int i,int j,int r)
{
 vis[i][j]=true;
 step++;
 if(r&1) map[i][j]='|';
 else map[i][j]='-'; 
 int x,y;
 is_max();
 x=i+dir[r][0];
 y=j+dir[r][1];
 if(vis[x][y]!=1){
   if(map[x][y]!='#' && x<n && y<n && x>=0 && y>=0)
    dfs(x,y,r);
   else //if(map[x][y]=='#' || !(x<n && y<n && x>=0 && y>=0))
   {   
    // is_max();
     int k=r&1;
     k=1-k;
    // --;
     x=i+dir[k][0];
     y=j+dir[k][1];
     if(!vis[x][y] && map[x][y]!='#' && x<n && y<n && x>=0 && y>=0)
     {
      map[i][j]='+';
      dfs(x,y,k);
      map[i][j]='.';
     }
     x=i+dir[k+2][0];
     y=j+dir[k+2][1];
     if(!vis[x][y] && map[x][y]!='#' && x<n && y<n && x>=0 && y>=0)
     {
      map[x][y]='+';
      dfs(x,y,k+2);
      map[x][y]='.';
     }
    //   step++;
   }
 }
 vis[i][j]=false;
 step--;
 map[i][j]='.';
}
int main()
{
     int i,j,k,des;
     ifstream fin("snail.in");
     ofstream fout("snail.out");
     cin>>n>>bn;
 memset(map,'.',sizeof(map));
 memset(vis,false,sizeof(vis));
 maxn=0;
 for(i=0;i<bn;i++)
 {
   cin>>bat;
   map[atoi(bat+1)-1][bat[0]-'A']='#';
 }
 
 dfs(0,0,0);
 dfs(0,0,1);
 maxmap[0][0]='S';
 fout<<maxn<<endl;
/* for(i=0;i<n;i++){
 // fout<<i+1<<' ';
   for(j=0;j<n;j++)
    fout<<maxmap[i][j];
   fout<<endl;
 }*/
     return 0;
}