题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1253
解题思路:
简单的三维广搜c;把握好坐标和数组的关系。
用了输入外挂c;然后加了几个小class="tags" href="/tags/YouHua.html" title=优化>优化:
1.曼哈顿距离class="tags" href="/tags/YouHua.html" title=优化>优化。
2.终点如果不能走c;直接结束-1.
做了这题c;对广搜又有了一点认识。
1.首先广搜是对每一个点只搜索一次c;每次搜索一个点后就不再走。所以不需要像以前那样判断是否已经入队。
2.搜索时候要加上边界c;这样就不用很多判断了。(一般都是用0做边界)
3.广搜的队列自己写比较快c;用数组模拟一下就可以了。
4.广搜的层数用一个结构体来保存c;每次入队时候c;说明层数要在这个点的基础上+1层。
代码如下:
<code class="language-cpp">#include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<algorithm> using namespace std; const int N = 55; const int dir[6][3] = {{0, 0, 1}, {0, 0, -1}, {-1, 0, 0}, {1, 0, 0}, {0, 1, 0}, {0, -1, 0}}; class="tags" href="/tags/STRUCT.html" title=struct>struct node { int x, y, z; int ceng; }que[50000]; int maze[N][N][N]; int a, b, c, t; int num; int head, tail; int Scan() { int res = 0 , ch; while( !( ( ch = getchar() ) >= '0' && ch <= '9' ) ) { if( ch == EOF ) return 1 << 30 ; } res = ch - '0' ; while( ( ch = getchar() ) >= '0' && ch <= '9' ) res = res * 10 + ( ch - '0' ) ; return res ; } int BFS() { node cur; cur.x = 1, cur.y = 1, cur.z = 1, cur.ceng = 0; maze[cur.x][cur.y][cur.z] = 0; que[tail++] = cur; while(head < tail) { node temp = que[head++]; if(temp.ceng > t) //无法到达 return -1; if(temp.x == a && temp.y == b && temp.z == c && temp.ceng <= t) return temp.ceng; for(int i = 0; i < 6; ++i) { node now; now.x = temp.x + dir[i][0]; now.y = temp.y + dir[i][1]; now.z = temp.z + dir[i][2]; if(maze[now.x][now.y][now.z]) { now.ceng = temp.ceng + 1; que[tail++] = now; maze[now.x][now.y][now.z] = 0; } } } return -1; } int main() { int ncase; ncase = Scan(); while(ncase--) { num = head = tail = 0; memset(maze, 0, sizeof(maze)); a = Scan(), b = Scan(), c = Scan(), t = Scan(); for(int i = 1; i <= a; ++i) for(int j = 1; j <= b; ++j) for(int k = 1; k <= c; ++k) { maze[i][j][k] = Scan() ^ 1; num += maze[i][j][k]; } if(maze[a][b][c] == 0 || num < a + b + c - 3) //终点无法走 { printf("-1\n"); continue; } printf("%d\n", BFS()); } return 0; }code>