| ||||||||||
| 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 | |||||||||
在线求助大牛: 为什么我下面的代码(含注释)会TLE,我用的是BFS,真的很奇怪!!感激不尽#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator