HDU-1240-Asteroids!

三维的BFS，和二维的差不多

[cpp] 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
char map[12][12][12]; 
int visit[12][12][12]; 
int ans[12][12][12]; 
int n; 
int dir[6][3]={{1,0,0},{-1,0,0},{0,-1,0},{0,1,0},{0,0,-1},{0,0,1}}; 
struct cam 
{ 
    int x; 
    int y; 
    int z; 
}list[1005]; 
int go(int x,int y,int z) 
{ 
    if(0<=x&&x<n&&0<=y&&y<n&&0<=z&&z<n&&map[x][y][z]=='O') 
    return 1; 
    return 0; 
} 
int bfs(int x1,int y1,int z1,int x2,int y2,int z2) 
{ 
    int head,tail; 
    int xx,yy,zz; 
    int i; 
    memset(visit,0,sizeof(visit)); 
    memset(ans,0,sizeof(ans)); 
    visit[x1][y1][z1]=1; 
    ans[x1][y1][z1]=0; 
    map[x2][y2][z2]='O'; 
    head=0; 
    tail=1; 
    list[0].x=x1; 
    list[0].y=y1; 
    list[0].z=z1; 
    while(head<tail) 
    { 
        x1=list[head].x; 
        y1=list[head].y; 
        z1=list[head].z; 
        if(x1==x2&&y1==y2&&z1==z2) 
        return ans[x2][y2][z2]; 
        for(i=0;i<6;i++) 
        { 
            xx=x1+dir[i][0]; 
            yy=y1+dir[i][1]; 
            zz=z1+dir[i][2]; 
            if(go(xx,yy,zz)&&!visit[xx][yy][zz]) 
            { 
                visit[xx][yy][zz]=1; 
                ans[xx][yy][zz]=ans[x1][y1][z1]+1; 
                list[tail].x=xx; 
                list[tail].y=yy; 
                list[tail].z=zz; 
                tail++; 
            } 
        } 
        head++; 
    } 
    return -1; 
} 
int main() 
{ 
    int x1,y1,z1; 
    int x2,y2,z2; 
    int i,j,sol; 
    char s[10]; 
    while(scanf("%s %d",s,&n)!=EOF) 
    { 
        for(i=0;i<n;i++) 
        for(j=0;j<n;j++) 
        scanf("%s",map[i][j]); 
        scanf("%d%d%d",&x1,&y1,&z1); 
        scanf("%d%d%d",&x2,&y2,&z2); 
        scanf("%s",s); 
        sol=bfs(x1,y1,z1,x2,y2,z2); 
        if(sol==-1) 
        printf("NO ROUTE/n"); 
        else 
        printf("%d %d/n",n,ans[x2][y2][z2]); 
    } 
    return 0; 
} 

 

作者：Cambridgeacm