nyoj 523 双向广搜

 

题目链接： http://acm.nyist.net/JudgeOnline/problem.php?pid=523

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
/*
    用普通搜索TLE，已知起点和终点，可以考虑双向广搜或A*算法加速搜索
    双向广搜，一个方向从出发点向终点搜索，一个方向从终点向出发点搜索，搜索到相同的结点时，即找到最短路径。 
*/
const int N = 52;
int dir[6][3] = {
    1,0,0,  -1,0,0,
    0,1,0,  0,-1,0,
    0,0,1,  0,0,-1
};
int mp[N][N][N];
int vis[N][N][N];//访问标记： 0没有访问过  1 被从开始到终点的方向访问过  2 被终到始的方向访问过
int step[N][N][N];
int h, m, n;
int times;
struct Node {
    int z, x, y;
    int step; 
    Node(int _z, int _x, int _y){
        z = _z; x = _x; y = _y;
    }
};

int bfs()
{
    if(mp[h-1][m-1][n-1] == 1) return -1;//终点可能是墙...
    memset(&vis[0][0][0], 0, sizeof(vis));
    memset(&step[0][0][0], 0, sizeof(step));
    Node start(0, 0, 0);
    vis[0][0][0] = 1;
    Node end(h-1, m-1, n-1);
    vis[h-1][m-1][n-1] = 2;
    queue<Node> que;
    que.push(start);
    que.push(end);
    while(!que.empty()){
        Node cur = que.front(); 
        que.pop();
        if(cur.step > times) continue;
        int cx = cur.x, cy = cur.y, cz= cur.z;
        for(int i=0; i<6; i++){
            int tx = cx+dir[i][0];
            int ty = cy+dir[i][1];
            int tz = cz+dir[i][2];
            if(tx <0 || tz<0 || ty<0 || tz>=h || tx>=m || ty >=n) continue;
            if(mp[tz][tx][ty] == 1) continue;
            if(vis[tz][tx][ty] == 0){
                Node next(tz, tx, ty);
                step[tz][tx][ty] = step[cz][cx][cy]+1;
                vis[tz][tx][ty] = vis[cz][cx][cy];//访问标记要保持一致
                que.push(next);
            } else if(vis[tz][tx][ty] != vis[cz][cx][cy]){//如果访问标记不一致，则说明来自不同方向上搜索的相遇的结点 
                return step[cz][cx][cy]+step[tz][tx][ty]+1 <= times? step[cz][cx][cy]+step[tz][tx][ty]+1: -1;
            }

        }
        
    }
    return -1;
}

int main()
{
    //INPUT;
    //OUTPUT;
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d%d", &h, &m, &n, &times);
        for(int i=0; i<h; i++){
            for(int j=0; j<m; j++){
                for(int k=0; k<n; k++){
                    scanf("%d", &mp[i][j][k]);
                }
            }
        }
        printf("%d\n", bfs());
    }

    return 0;
}