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 Ren_Bocheng at 2015-08-15 14:22:29 on Problem 2251
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;

int vis[31][31][31];
char Map[31][31][31];
int step[35][35][35];
int l,r,c;
int dir[6][3]={1,0,0, -1,0,0, 0,1,0, 0,-1,0, 0,0,1, 0,0,-1};

struct point
{
    int x,y,z;
} in,out,beg;

int check(int x, int y, int z)
{
    if(!vis[z][x][y]&&z >= 0&&z < l&&x >= 0&&x < r&&y >= 0&&y < c&&Map[z][x][y]!='#')
        return 1;
    return 0;
}

int bfs()
{
    memset(vis, 0, sizeof(vis));
    memset(step, 0, sizeof(step));
    vis[beg.z][beg.x][beg.y] = 1;
    step[beg.z][beg.x][beg.y] = 0;
    queue<point>q;
    q.push(beg);
    while(!q.empty())
    {
        out = q.front();
        q.pop();
        for(int i = 0; i < 6; ++i)
        {
            in.z = out.z+dir[i][0];
            in.x = out.x+dir[i][1];
            in.y = out.y+dir[i][2];
            if(check(in.x, in.y, in.z))
            {
                if(Map[in.z][in.x][in.y]=='E')
                    return step[out.z][out.x][out.y]+1;
                q.push(in);
                vis[in.z][in.x][in.y] = 1;
                step[in.z][in.x][in.y] = step[out.z][out.x][out.y] + 1;
            }
        }
    }
    return -1;
}

int main()
{
    while(~scanf("%d%d%d", &l,&r,&c))
    {
        if(!l&&!r&&!c)break;
        for(int i = 0; i < l; ++i)
            for(int j = 0; j < r; ++j)
                scanf("%s", Map[i][j]);
        for(int i = 0; i < l; ++i)
            for(int j = 0; j < r; ++j)
                for(int k = 0; k < c; ++k)
                    if(Map[i][j][k]=='S')
                    {
                        beg.z = i;
                        beg.x = j;
                        beg.y = k;
                    }
        int ans = bfs();
        ans==-1?printf("Trapped!\n"):printf("Escaped in %d minute(s).\n", ans);
    }
    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