[题解]USACO 5.2.1 Snail Trails

链接：http://cerberus.delos.com:791/usacoprob2?S=snail&a=uzElkgTaI9d
描述：有障碍的棋盘上的搜索，求从左上角出发最多经过多少个格子。
思路：暴搜
我的实现：
  1 /*
  2 ID:zhangyi20
  3 PROG:snail
  4 LANG:C++
  5 */
  6 #include <iostream>
  7 #include <cstdio>
  8 #include <cmath>
  9 using namespace std;
 10 #define MaxN 120
 11 int N,B;
 12 int mat[MaxN+5][MaxN+5];//0空地 1障碍 2走过
 13 int Dfs(int i,int j,int Dir)//方向：0向上，1向右，2向下，3向左
 14 {
 15     mat[i][j]=2;
 16     int Ret=0,i_=i,j_=j;
 17     int tmp1=-1,tmp2=-1;
 18     if(Dir==0)//向上
 19     {
 20         for(i=i-1; ;--i,++Ret)
 21         {
 22             if(mat[i][j])
 23                 break;
 24             mat[i][j]=2;
 25         }
 26         if(mat[i][j]==1)//转向
 27         {
 28             if(mat[i+1][j-1])
 29                 tmp1=0;
 30             else
 31                 tmp1=Dfs(i+1,j,3);
 32             if(mat[i+1][j+1])
 33                 tmp2=0;
 34             else
 35                 tmp2=Dfs(i+1,j,1);
 36             Ret+=max(tmp1,tmp2);
 37         }
 38         for(i=i+1;i<=i_;++i)
 39             mat[i][j]=0;
 40     }
 41     else if(Dir==1)//向右
 42     {
 43         for(j=j+1; ;++j,++Ret)
 44         {
 45             if(mat[i][j])
 46                 break;
 47             mat[i][j]=2;
 48         }
 49         if(mat[i][j]==1)//转向
 50         {
 51             if(mat[i-1][j-1])
 52                 tmp1=0;
 53             else
 54                 tmp1=Dfs(i,j-1,0);
 55             if(mat[i+1][j-1])
 56                 tmp2=0;
 57             else
 58                 tmp2=Dfs(i,j-1,2);
 59                 Ret+=max(tmp1,tmp2);
 60         }
 61         for(j=j-1;j>=j_;--j)
 62             mat[i][j]=0;
 63     }
 64     else if(Dir==2)//向下
 65     {
 66         for(i=i+1; ;++i,++Ret)
 67         {
 68             if(mat[i][j])
 69                 break;
 70             mat[i][j]=2;
 71         }
 72         if(mat[i][j]==1)//转向
 73         {
 74             if(mat[i-1][j-1])
 75                 tmp1=0;
 76             else
 77                 tmp1=Dfs(i-1,j,3);
 78             if(mat[i-1][j+1])
 79                 tmp2=0;
 80             else
 81                 tmp2=Dfs(i-1,j,1);
 82             Ret+=max(tmp1,tmp2);
 83         }
 84         for(i=i-1;i>=i_;--i)
 85             mat[i][j]=0;
 86     }
 87     else//向左
 88     {
 89         for(j=j-1; ;--j,++Ret)
 90         {
 91             if(mat[i][j])
 92                 break;
 93             mat[i][j]=2;
 94         }
 95         if(mat[i][j]==1)//转向
 96         {
 97             if(mat[i-1][j+1])
 98                 tmp1=0;
 99             else
100                 tmp1=Dfs(i,j+1,0);
101             if(mat[i+1][j+1])
102                 tmp2=0;
103             else
104                 tmp2=Dfs(i,j+1,2);
105             Ret+=max(tmp1,tmp2);
106         }
107         for(j=j+1;j<=j_;++j)
108             mat[i][j]=0;
109     }
110     return Ret;
111 }
112 int main()
113 {
114     freopen("snail.in","r",stdin);
115     freopen("snail.out","w",stdout);
116     scanf("%d%d",&N,&B);
117     int i,j;
118     char c;
119     for(i=1;i<=B;++i)
120     {
121         do
122         {
123             scanf("%c",&c);
124         }while(c<'A'||c>'Z');
125         scanf("%d",&j);
126         mat[j][c-'A'+1]=1;
127     }
128     for(i=1;i<=N;++i)
129         mat[0][i]=mat[N+1][i]=mat[i][0]=mat[i][N+1]=1;//给地图四周打上障碍
130     mat[1][1]=2;
131     printf("%d
",max(Dfs(1,1,1),Dfs(1,1,2))+1);
132     return 0;
133 }
View Code