链接：http://cerberus.delos.com:791/usacoprob2?S=snail&a=uzElkgTaI9d

描述：有障碍的棋盘上的搜索，求从左上角出发最多经过多少个格子。

思路：暴搜

我的实现：

1 /*
2 ID:zhangyi20
3 PROG:snail
4 LANG:C++
5 */
6 #include
7 #include
8 #include
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\n",max(Dfs(1,1,1),Dfs(1,1,2))+1);
132 return 0;
133 }