Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

挺好玩的,三维的bfs

Posted by 14110572101 at 2015-08-16 16:02:43 on Problem 2251
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <vector>
#include <cstdio>
#include <map>
#include <set>
const int INF = 0x3f3f3f3f;

using namespace std;

char Map[35][35][35];
bool vis[35][35][35];
int dx[]={1,-1,0,0,0,0};
int dy[]={0,0,1,-1,0,0};
int dz[]={0,0,0,0,1,-1};
int x,y,z;
struct node
{
    int x,y,z;
    int t;
}ans,ant;
bool bfs()
{
    ans.t = 0;
    queue<node>Q;
    Q.push(ans);
    vis[ans.x][ans.y][ans.z] = true;
    while(!Q.empty())
    {
        ant = Q.front();Q.pop();
        if(Map[ant.x][ant.y][ant.z] == 'E')
        {
            printf("Escaped in %d minute(s).\n",ant.t);
            return false;
        }
        for(int i=0;i<6;i++)
        {
            ans.x = ant.x+dx[i];
            ans.y = ant.y+dy[i];
            ans.z = ant.z+dz[i];
            ans.t = ant.t + 1;
            if(ans.x>=0&&ans.y>=0&&ans.z>=0&&ans.x<x&&ans.y<y&&ans.z<z&&!vis[ans.x][ans.y][ans.z]&&Map[ans.x][ans.y][ans.z]!='#')
            {
                Q.push(ans);
                vis[ans.x][ans.y][ans.z] = true;
            }
        }
    }
    return true;
}

int main()
{
    while(~scanf("%d %d %d",&x,&y,&z) && (x||y||z))
    {
        for(int i=0;i<x;i++)
        {
            for(int j=0;j<y;j++)
            {
                scanf("%s",Map[i][j]);
                for(int k=0;k<z;k++)
                {
                    if(Map[i][j][k] == 'S')
                    {
                        ans.x = i;ans.y = j;ans.z = k;
                    }
                }
            }
        }
        memset(vis,false,sizeof(vis));
        if(bfs())
            printf("Trapped!\n");
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator