| ||||||||||
| 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