Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
深搜+广搜,1A,贴代码#include<stdio.h> #include<memory.h> int p,q; char field[41][41]; int visited[41][41]; int bx,by,ex,ey; int direct[4][2] = {{-1,0},{0,-1},{1,0},{0,1}}; //left,up.right,down int cur_dir; int left_num = 0,right_num = 0; int s_path = 0; void dfs_left(int x,int y) { if(field[x][y] == 'E') return; int t_cur,tx,ty; for(int i = -1 ; i <= 2 ; i ++) { t_cur = (cur_dir + i + 4) % 4; tx = x + direct[t_cur][0]; ty = y + direct[t_cur][1]; if(tx < 0 || tx >= p || ty < 0 || ty >= q) continue; if((field[tx][ty] == '.' || field[tx][ty] == 'E')) break; } cur_dir = t_cur; left_num ++; dfs_left(tx,ty); } void dfs_right(int x,int y) { if(field[x][y] == 'E') return; int t_cur,tx,ty; for(int i = 1 ; i >= -2 ; i --) { t_cur = (cur_dir + i + 4) % 4; tx = x + direct[t_cur][0]; ty = y + direct[t_cur][1]; if(tx < 0 || tx >= p || ty < 0 || ty >= q) continue; if((field[tx][ty] == '.' || field[tx][ty] == 'E')) break; } cur_dir = t_cur; right_num ++; dfs_right(tx,ty); } struct Node { Node(){} Node(int xx,int yy) { x = xx; y = yy; } int x,y; }; Node node[1601]; void bfs() { int head = 0,tail = 0; node[tail ++] = Node(bx,by); visited[bx][by] = 0; while(head != tail) { Node t = node[head ++]; head = head % 1600; for(int i = 0 ; i < 4 ; i ++) { int xx = t.x + direct[i][0]; int yy = t.y + direct[i][1]; if(xx < 0 || xx >= p || yy < 0 || yy >= q || field[xx][yy] == '#') continue; if(visited[xx][yy] == -1) { visited[xx][yy] = visited[t.x][t.y] + 1; node[tail ++] = Node(xx,yy); if(xx == ex && yy == ey) return; } } } } int main() { int test; scanf("%d",&test); for(int i = 0 ; i < test ; i ++) { memset(visited,-1,sizeof(visited)); scanf("%d%d",&p,&q); for(int j = 0 ; j < q ; j ++) { while(getchar() != '\n'); for(int k = 0 ; k < p ; k ++) { scanf("%c",&field[k][j]); if(field[k][j] == 'S') { bx = k; by = j; if(bx == 0) cur_dir = 2; if(bx == p - 1) cur_dir = 0; if(by == 0) cur_dir = 3; if(by == q - 1) cur_dir = 1; } if(field[k][j] == 'E') { ex = k; ey = j; } } } int t = cur_dir; left_num = 0; dfs_left(bx,by); left_num ++; printf("%d ",left_num); cur_dir = t; right_num = 0; dfs_right(bx,by); right_num ++; printf("%d ",right_num); bfs(); printf("%d\n",visited[ex][ey] + 1); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator