|
|
Posted on 2008-10-10 14:54 Hero 阅读(98) 评论(0) 编辑 收藏 引用 所属分类: 代码如诗－－ACM
1 /*
2 ID: wangzha4
3 LANG: C++
4 TASK: snail
5 */
6 /*
7 Executing
8 Test 1: TEST OK [0.000 secs, 2892 KB]
9 Test 2: TEST OK [0.011 secs, 2892 KB]
10 Test 3: TEST OK [0.000 secs, 2888 KB]
11 Test 4: TEST OK [0.000 secs, 2888 KB]
12 Test 5: TEST OK [0.011 secs, 2888 KB]
13 Test 6: TEST OK [0.000 secs, 2892 KB]
14 Test 7: TEST OK [0.011 secs, 2892 KB]
15 Test 8: TEST OK [0.000 secs, 2888 KB]
16 Test 9: TEST OK [0.000 secs, 2888 KB]
17 Test 10: TEST OK [0.022 secs, 2892 KB]
18 Test 11: TEST OK [0.000 secs, 2888 KB]
19 Test 12: TEST OK [0.065 secs, 2888 KB]
20 */
21 #include <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24
25 const int size = 150 ;
26 int data[size][size] ;
27 int flag[size][size] ;
28
29 int inn, num ;
30 int best ;
31
32 bool Indata( int r, int c )
33 {
34 if( r>=1&&r<=inn&&c>=1&&c<=inn ) return true ;
35 else return false ;
36 }
37
38 void DFS( int r, int c, int incr, int incc, int step )
39 {
40 if( 1 == flag[r][c] )
41 {
42 best = best > step ? best : step ;
43 return ;
44 }
45
46 flag[r][c] = 1 ;
47
48 if( Indata(r+incr, c+incc)&&0==data[r+incr][c+incc] )
49 {
50 DFS( r+incr, c+incc, incr, incc, step+1 ) ;
51 }
52 else
53 {
54 if( Indata(r+1, c+0)&&0==data[r+1][c+0] ) DFS( r+1, c+0, 1, 0, step+1 ) ;
55 if( Indata(r+0, c-1)&&0==data[r+0][c-1] ) DFS( r+0, c-1, 0, -1, step+1 ) ;
56 if( Indata(r-1, c+0)&&0==data[r-1][c+0] ) DFS( r-1, c+0, -1, 0, step+1 ) ;
57 if( Indata(r+0, c+1)&&0==data[r+0][c+1] ) DFS( r+0, c+1, 0, 1, step+1 ) ;
58 }
59
60 flag[r][c] = 0 ;
61
62 }
63
64 int main()
65 {
66 freopen( "snail.in", "r", stdin ) ;
67 freopen( "snail.out","w",stdout ) ;
68
69 //freopen( "in.txt", "r", stdin ) ;
70 //freopen( "out.txt","w",stdout ) ;
71
72 scanf( "%d %d", &inn, &num ) ; getchar() ;
73 //printf( "inn==%d, num==%d\n", inn, num ) ;
74 memset( flag, 0, sizeof(flag) ) ;
75 memset( data, 0, sizeof(data) ) ;
76
77 int row ; char col ;
78 for( int i=1; i<=num; i++ )
79 {
80 scanf( "%c%d", &col, &row ) ; getchar() ;
81 //printf( "col==%c, row==%d\n", col, row ) ;
82 data[row][col-'A'+1] = 1 ;
83 }
84
85 best = -1 ;
86
87 DFS( 1, 1, 0, 1, 0 ) ;
88
89 DFS( 1, 1, 1, 0, 0 ) ;
90
91 printf( "%d\n", best ) ;
92
93
94 return 0 ;
95 }
|