Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

求大神帮忙优化一下,超时了。

Posted by tiankangwei at 2011-06-27 19:37:47 on Problem 3083
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator