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

在线求助大牛: 为什么我下面的代码(含注释)会TLE,我用的是BFS,真的很奇怪!!感激不尽

Posted by gfedcba at 2009-03-03 15:31:13 on Problem 2251 and last updated at 2009-03-03 15:32:17
#include <iostream>
#include <queue>
using namespace std;

struct node 
{
	int i;
	int j;
	int k;
	int steps; // 记录当前的移动步数
};
queue<node> Q;

int level , row, col;

const int N = 30;
// 第一维层,第二维行,第三维列
char matrix[N][N][N];

// 6个移动方向,move[][0]表示层, move[][1]表示行, move[][2]表示列
int move[][3] = {{0, 0, -1} , {0, 0, 1} , {0, -1, 0}, {0, 1, 0}, {-1, 0, 0}, {1, 0, 0} };

// 判断所在位置是否合法
bool isOk(int i, int j, int k)
{
	if (i>=0 && i<=level-1 && j>=0 && j<=row-1 && k>=0 && k<=col-1 && matrix[i][j][k] != '#')
	{
		return true;
	}
	else
	{
		return false;
	}

}

// 广度优先搜索
int bfs(int i, int j, int k)
{
	node front, rear;

	front.i = i;
	front.j = j;
	front.k = k;
	front.steps = 0;
	Q.push(front);

	while (!Q.empty())
	{
		front = Q.front();
		Q.pop();

		for (i=0; i<=6-1; i++)
		{
			rear.i = front.i+move[i][0];
			rear.j = front.j+move[i][1];
			rear.k = front.k+move[i][2];
			rear.steps = front.steps+1;

			if (isOk(rear.i, rear.j, rear.k))
			{
				// 若找到出口,返回最少的移动步数
				if (matrix[rear.i][rear.j][rear.k] == 'E')
				{
					return rear.steps;
				}
				else
				{
					Q.push(rear);
				}
			}
		} // end of for 
	}// end of while

	// 若队列为空,表示找不到出口,返回0,表示移动步数为0,也即原地不动
	return 0;

}
int main()
{
	int i, j, k;
	
	int startl, startr, startc;
        while( cin>>level>>row>>col && (level|row|col) != 0)
	{
		for (i=0; i<=level-1; i++)
		{
			for (j=0; j<=row-1; j++)
			{
				scanf("%s", &matrix[i][j]); // 整行输入,提高效率
				for (k=0; k<=col-1; k++)
				{
				/*	scanf("%c", &matrix[i][j][k]);*/
					if (matrix[i][j][k] == 'S' )
					{
						startl = i;
						startr = j;
						startc = k;
					}
				}	
			}
		}

		int ans = bfs(startl, startr, startc);

		if (ans == 0) // 若移动步数为0,表示原地不动
		{
			printf("Trapped!\n");
		}
		else
		{
			printf("Escaped in %d minute(s).\n", ans);
		}
	}
    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