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