我希望你是我独家记忆

一段永远封存的记忆,随风而去
posts - 263, comments - 31, trackbacks - 0, articles - 3
   :: 首页 :: 新随笔 ::  :: 聚合  :: 管理

P3083——深搜+广搜

Posted on 2008-09-02 10:35 Hero 阅读(341) 评论(0)  编辑 收藏 引用 所属分类: 代码如诗--ACM
  1 //3083 Accepted 416K 16MS G++ 5141B PKU Children of the Candy Corn
  2 
  3 //深搜 + 广搜
  4 
  5 #include <stdio.h>
  6 #include <stdlib.h>
  7 #include <string.h>
  8 
  9 const int size = 50 ;
 10 char data[size][size] ;
 11 int flag[size][size] ;
 12 
 13 struct QUE
 14 {
 15     int r ;
 16     int c ;
 17     int step ;
 18 };
 19 struct QUE que[100000] ;
 20 int head, tail ;
 21 
 22 int ldir[5][3] ; int rdir[5][3] ;//左右方向
 23 int udir[5][3] ; int ddir[5][3] ;//上下方向
 24 
 25 int innum ;
 26 int inrow, incol ;
 27 
 28 int snr, snc ;
 29 int enr, enc ;
 30 
 31 int rval, lval, minval ; bool OK ;
 32 
 33 void input()
 34 {
 35     scanf( "%d %d"&incol, &inrow ) ;
 36 
 37     forint i=1; i<=inrow; i++ ) 
 38     {
 39         scanf( "%s", data[i]+1 ) ; //printf( "%s\n", data[i]+1 ) ;
 40     }
 41 
 42     forint r=1; r<=inrow; r++ )
 43     {
 44         forint c=1; c<=incol; c++ )
 45         {
 46             if'S' == data[r][c] ) { snr = r , snc = c ; }
 47             if'E' == data[r][c] ) { enr = r , enc = c ; }
 48         }
 49     }
 50 }
 51 
 52 bool fin( int r, int c )
 53 {
 54     if( r>=1 && r<=inrow && c>=1 && c<=incol )    return true ;
 55     else return false ;
 56 }
 57 
 58 void DFS_left( int sr, int sc, int d, int step )
 59 {
 60     if( OK )    return ;
 61     if(  'E' == data[sr][sc] )
 62     {
 63         lval = step ; OK = true ; return ;
 64     }
 65 
 66     int nextr = sr+ldir[d][0] ; int nextc = sc+ldir[d][1] ; int curd = ldir[d][2] ;
 67     if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
 68         DFS_left( nextr, nextc, curd, step+1 ) ;
 69 
 70     if( OK )    return ;
 71 
 72     nextr = sr+udir[d][0] ; nextc = sc+udir[d][1] ; curd = d ;
 73     if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
 74         DFS_left( nextr, nextc, curd, step+1 ) ;
 75 
 76     if( OK )    return ;
 77 
 78     nextr = sr+rdir[d][0] ; nextc = sc+rdir[d][1] ; curd = rdir[d][2] ;
 79     if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
 80         DFS_left( nextr, nextc, curd, step+1 ) ;
 81 
 82     if( OK )    return ;
 83 
 84     nextr = sr+ddir[d][0] ; nextc = sc+ddir[d][1] ; curd = 5-d ;
 85     DFS_left( nextr, nextc, curd, step+1 ) ;
 86 }
 87 
 88 void DFS_right( int sr, int sc, int d, int step )
 89 {
 90     if( OK )    return ;
 91     if(  'E' == data[sr][sc] )
 92     {
 93         rval = step ; OK = true ; return ;
 94     }
 95 
 96     int nextr = sr+rdir[d][0] ; int nextc = sc+rdir[d][1] ; int curd = rdir[d][2] ;
 97     if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
 98         DFS_right( nextr, nextc, curd, step+1 ) ;
 99 
100     if( OK )    return ;
101 
102     nextr = sr+udir[d][0] ; nextc = sc+udir[d][1] ; curd = d ;
103     if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
104         DFS_right( nextr, nextc, curd, step+1 ) ;
105 
106     if( OK )    return ;
107 
108     nextr = sr+ldir[d][0] ; nextc = sc+ldir[d][1] ; curd = ldir[d][2] ;
109     if( fin(nextr, nextc) && ('.'==data[nextr][nextc]||'E'==data[nextr][nextc] ) )
110         DFS_right( nextr, nextc, curd, step+1 ) ;
111 
112     if( OK )    return ;
113 
114     nextr = sr+ddir[d][0] ; nextc = sc+ddir[d][1] ; curd = 5-d ;
115     DFS_right( nextr, nextc, curd, step+1 ) ;
116 }
117 
118 void left()
119 {
120     int direct ;
121     if1 == snr ) direct = 4 ; 
122     if1 == snc ) direct = 3 ; 
123     if( inrow == snr ) direct = 1 ; 
124     if( incol == snc ) direct = 2 ; 
125 
126     OK = false ;
127     DFS_left( snr, snc, direct, 1 ) ;
128 }
129 void right()
130 {
131     int direct ;
132     if1 == snr ) direct = 4 ; 
133     if1 == snc ) direct = 3 ; 
134     if( inrow == snr ) direct = 1 ; 
135     if( incol == snc ) direct = 2 ; 
136 
137     OK = false ;
138     DFS_right( snr, snc, direct, 1 ) ;
139 }
140 void init()
141 {
142     ldir[1][0= 0 ;  ldir[1][1= -1 ;   ldir[1][2= 2 ;//1
143     ldir[2][0= 1 ;  ldir[2][1= 0 ;    ldir[2][2= 4 ;
144     ldir[3][0= -1 ; ldir[3][1= 0 ;    ldir[3][2= 1 ;
145     ldir[4][0= 0 ;  ldir[4][1= 1 ;    ldir[4][2= 3 ;
146 
147     rdir[1][0= 0 ;   rdir[1][1= 1 ;   rdir[1][2= 3 ;//1
148     rdir[2][0= -1 ;  rdir[2][1= 0 ;   rdir[2][2= 1 ;
149     rdir[3][0= 1 ;   rdir[3][1= 0 ;   rdir[3][2= 4 ;
150     rdir[4][0= 0 ;   rdir[4][1= -1 ;  rdir[4][2= 2 ;
151 
152     udir[1][0= -1 ;  udir[1][1= 0 ;   udir[1][2= 3 ;//1
153     udir[2][0= 0 ;   udir[2][1= -1 ;  udir[2][2= 1 ;
154     udir[3][0= 0 ;   udir[3][1= 1 ;   udir[3][2= 4 ;
155     udir[4][0= 1 ;   udir[4][1= 0 ;   udir[4][2= 2 ;
156 
157     ddir[1][0= 1 ;   ddir[1][1= 0 ;   ddir[1][2= 3 ;//1
158     ddir[2][0= 0 ;   ddir[2][1= 1 ;   ddir[2][2= 1 ;
159     ddir[3][0= 0 ;   ddir[3][1= -1 ;  ddir[3][2= 4 ;
160     ddir[4][0= -1 ;  ddir[4][1= 0 ;   ddir[4][2= 2 ;
161 }
162 
163 void BFS()
164 {
165     memset( flag, 0sizeof(flag) ) ;
166     head = tail = 0 ; int curr ; int curc ;
167     que[tail].r = snr ; que[tail].c = snc ; que[tail++].step = 1 ; flag[snr][snc] = 1 ;
168 
169     while( head < tail )
170     {
171         curr = que[head].r ; curc = que[head].c ;
172 
173         if'E' == data[curr][curc] ) { minval = que[head].step ; return ; }
174 
175         forint i=1; i<=4; i++ ) {
176             curr = que[head].r+rdir[i][0] ; curc = que[head].c+rdir[i][1] ;
177             if( fin(curr, curc) && 0==flag[curr][curc]&&'.'==data[curr][curc]||'E'==data[curr][curc] )
178             {
179                 flag[curr][curc] = 1 ; que[tail].r = curr ; que[tail].c = curc ; que[tail++].step = que[head].step+1 ;
180             }
181         }
182         head++ ;
183     }
184 }
185 
186 void process()
187 {
188     init() ;
189 
190     left() ;
191 
192     right() ;
193 
194     BFS() ;
195 
196     printf( "%d %d %d\n", lval, rval, minval ) ;
197 }
198 
199 int main()
200 {
201     //freopen( "in.txt", "r", stdin ) ;
202 
203     while( scanf( "%d"&innum ) != EOF )
204     {
205         forint ct=1; ct<=innum; ct++ )
206         {
207             input() ;
208 
209             process() ;
210 
211             //output() ;
212         }
213     }
214 
215     return 0 ;
216 }

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理