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 |
求大神帮忙优化一下,超时了。#include <queue> #include <cstdio> using namespace std; int dir[4][2] = { {0,-1}, {1,0}, {0,1}, {-1,0} }; int start_i, start_j, end_i, end_j, w, h, n; struct point { int flag, way, step, x, y; bool check; } map[41][41]; int dfs_R ( int x, int y ) { int temp; if ( x == end_i && y == end_j ) return map[x][y].step; for ( int i = ( map[x][y].way + 3 ) % 4; ; i++ ) { temp = i % 4; int a = x + dir[temp][0]; int b = y + dir[temp][1]; if ( a < h && a >= 0 && b < w && b >= 0 && map[a][b].flag ) { map[a][b].way = temp; map[a][b].step = map[x][y].step + 1; return dfs_R(a,b); } } } int dfs_L ( int x, int y ) { int temp; if ( x == end_i && y == end_j ) return map[x][y].step; for ( int i = ( map[x][y].way + 5 ) % 4 + 4; ; i-- ) { temp = i % 4; int a = x + dir[temp][0]; int b = y + dir[temp][1]; if ( a < h && a >= 0 && b < w && b >= 0 && map[a][b].flag ) { map[a][b].way = temp; map[a][b].step = map[x][y].step + 1; return dfs_L(a,b); } } } int bfs() { queue<point> Q; point current, next; current.step = 1; current.check = true; current.x = start_i; current.y = start_j; Q.push ( current ); while ( ! Q.empty () ) { current = Q.front (); Q.pop (); if ( current.x == end_i && current.y == end_j ) return current.step; for ( int i = 0; i < 4; i++ ) { int a = current.x + dir[i][0]; int b = current.y + dir[i][1]; if ( ! map[a][b].check && a < h && a >= 0 && b < w && b >= 0 && map[a][b].flag ) { next.x = a; next.y = b; next.check = true; next.step = current.step + 1; Q.push ( next ); } } } } int main() { char str[41]; scanf("%d",&n); while ( n-- ) { scanf("%d%d",&w,&h); memset(map,0,sizeof(map)); for ( int i = 0; i < h; i++ ) { scanf("%s",&str); for ( int j = 0; j < w; j++ ) { if ( str[j] == 'S' ) { start_i = i; start_j = j; map[i][j].flag = 1; } else if ( str[j] == 'E' ) { end_i = i; end_j = j; map[i][j].flag = 1; } else if ( str[j] == '.' ) map[i][j].flag = 1; else map[i][j].flag = 0; } } if ( start_i == 0 ) map[start_i][start_j].way = 1; else if ( start_i == h-1 ) map[start_i][start_j].way = 3; else if ( start_j == 0 ) map[start_i][start_j].way = 2; else if ( start_j == w-1 ) map[start_i][start_j].way = 0; map[start_i][start_j].step = 1; printf( "%d %d %d\n",dfs_L(start_i,start_j), dfs_R(start_i,start_j), bfs() ); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator