Asteroids! hdu 1240

一时失言乱红尘 2021-11-02 14:32 141阅读 0赞

三维空间的简单BFS....

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <queue>
    #include <iostream>
    
    using namespace std;
    
    char map[20][20][20];
    int N, a, b, c, d, e, f, f1;
    
    int xx[ ] = {
         0, 1, 0, -1, 0, 0};
    int yy[ ] = {
         1, 0, -1, 0, 0, 0};
    int zz[ ] = {
         0, 0, 0, 0 , 1, -1};
    
    struct node
    {
         
    int x, y, z, t;
    }Nd;
    
    int judge( int x, int y, int z)
    {
         
    if ( x < 0 || x >= N || y < 0 || y >= N || z <0 || z >= N)
    return 0;
    return 1;
    }
    
    void BFS( )
    {
         
    int i, j, x1, x2, z1, y1, y2, z2, t1,t2;
        Nd.x = a, Nd.y = b, Nd.z = c, Nd.t = 0;
        queue<node>q;
        q.push(Nd);
        f1 = 0;
    while (!q.empty( ))
        {
         
            Nd = q.front( );
            q.pop( );
            x1 = Nd.x, y1 = Nd.y, z1 = Nd.z, t1 = Nd.t;
    if (x1 == d && y1 == e && z1 == f)
             {      
                    f1 = 1;
                    printf("%d %d\n",N, t1);
    break;
             }
    //printf("%d\n",N);
            for (i = 0; i < 6; i++)
            {
         
                x2 = x1 + xx[i];
                y2 = y1 + yy[i];
                z2 = z1 + zz[i];
    //printf("(%d,%d,%d)-> %c %d \n",x2, y2, z2, map[x2][y2][z2], judge(x2, y2, z2));
                if ( judge(x2, y2, z2) && map[x2][y2][z2] != 'X' )
                  {
         
                        map[x2][y2][z2] = 'X';
                        Nd.x = x2, Nd.y = y2, Nd.z = z2, Nd.t = t1 + 1;
    //    printf("into:%d %d %d\n",x2, y2, z2);
                        q.push(Nd);
                  }
            }
    
        }
    }
    
    
    
    
    
    
    
    int main(  )
    {
         
    char ch[10];
    
    int i, j, z;
    
    while (scanf("%s%d",ch, &N) != EOF)
        {   
    for (z = 0; z < N; z++)
    for (i = 0; i < N; i++)
    for(j = 0; j < N; j++)
                    cin>>map[i][j][z];
            scanf("%d%d%d",&a, &b, &c);
            scanf("%d%d%d",&d, &e, &f);
            scanf("%s",ch);
            BFS( );
    if (!f1)
                puts("NO ROUTE");
    
        }
    return 0;
    }

转载于:https://www.cnblogs.com/tangcong/archive/2011/08/09/2132674.html