POJ 3322 Bloxorz I 三维BFS

本来只是打算为今晚的CF热热手的,结果选了道坑爹的BFS。写了350多行的代码还WA了一次。。。。。

对于普通的方格有五种情况,如下图所示,对于方格5来说,与1,与2,与3,与4组成的矩形为四种不同的情况,还有一种为竖直站立的情况。

对于Easily Broken Cell只存在前四种情况。

POJ  3322 Bloxorz I   三维BFS

很显然第三维标记这几种情况即可。思路还算简单,代码写的比较麻烦了。。。。

话说今年大年三十哇,出去耍会先。


#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <cmath>
#include <algorithm>

#define LL long long
#define PI (acos(-1.0))
#define EPS (1e-8)

using namespace std;

const int MAXN = 1001000;

bool mark[510][510][5];

char Map[510][510];

struct N
{
    int x,y,ty,ans;
};

int jx[] = {-1, 0, 1, 0};
int jy[] = { 0,-1, 0, 1};

void bfs(int n,int m)
{
    int i,j;

    queue<N> q;

    N s,t;

    memset(mark,false,sizeof(mark));

    for(i = 1,j = m+1;i < n && j == m+1; ++i)
    {
        for(j = 1;j <= m && Map[i][j] != ‘X‘; ++j)
            ;
    }

    s.x = i-1,s.y = j;

    for(i = 0;i < 4 && Map[s.x+jx[i]][s.y+jy[i]] != ‘X‘; ++i)
        ;

    s.ty = i;
    s.ans = 0;

    mark[s.x][s.y][s.ty] = true;

    q.push(s);

    while(q.empty() == false)
    {
        s = q.front();
        q.pop();

        if(Map[s.x][s.y] == ‘O‘ && s.ty == 4)
        {
            cout<<s.ans<<endl;
            return ;
        }

        if(s.ty == 0)
        {
            if(s.x-2 >= 1 && Map[s.x-2][s.y] != ‘#‘ && Map[s.x-2][s.y] != ‘E‘ && mark[s.x-2][s.y][4] == false)
            {
                t.ty = 4;
                t.x = s.x-2;
                t.y = s.y;
                t.ans = s.ans + 1;

                mark[s.x-2][s.y][4] = true;

                q.push(t);
            }

            if(s.x+1 <= n && Map[s.x+1][s.y] != ‘#‘ && Map[s.x+1][s.y] != ‘E‘ && mark[s.x+1][s.y][4] == false)
            {
                t.ty = 4;
                t.x = s.x+1;
                t.y = s.y;
                t.ans = s.ans+1;

                mark[s.x+1][s.y][4] = true;

                q.push(t);

            }

            if(s.y+1 <= m && s.x-1 >= 1 && Map[s.x][s.y+1] != ‘#‘ && Map[s.x-1][s.y+1] != ‘#‘ && mark[s.x][s.y+1][0] == false && mark[s.x-1][s.y+1][2] == false)
            {
                t.ty = 0;
                t.x = s.x;
                t.y = s.y+1;
                t.ans = s.ans+1;

                mark[s.x][s.y+1][0] = true ;
                mark[s.x-1][s.y+1][2] = true ;

                q.push(t);
            }

            if(s.y-1 >= 1 && s.x-1 >= 1 && Map[s.x][s.y-1] != ‘#‘ && Map[s.x-1][s.y-1] != ‘#‘ && mark[s.x][s.y-1][0] == false && mark[s.x-1][s.y-1][2] == false)
            {
                t.ty = 0;
                t.x = s.x;
                t.y = s.y-1;
                t.ans = s.ans+1;

                mark[s.x][s.y-1][0] = true ;
                mark[s.x-1][s.y-1][2] = true ;

                q.push(t);
            }
        }
        else if(s.ty == 1)
        {
            if(s.y-2 >= 1 && Map[s.x][s.y-2] != ‘#‘ && Map[s.x][s.y-2] != ‘E‘ && mark[s.x][s.y-2][4] == false)
            {
                t.ty = 4;
                t.x = s.x;
                t.y = s.y-2;
                t.ans = s.ans + 1;

                mark[s.x][s.y-2][4] = true;

                q.push(t);
            }

            if(s.y+1 <= m && Map[s.x][s.y+1] != ‘#‘ && Map[s.x][s.y+1] != ‘E‘ && mark[s.x][s.y+1][4] == false)
            {
                t.ty = 4;
                t.x = s.x;
                t.y = s.y+1;
                t.ans = s.ans+1;

                mark[s.x][s.y+1][4] = true;

                q.push(t);

            }

            if(s.y-1 >= 1 && s.x+1 <= n && Map[s.x+1][s.y] != ‘#‘ && Map[s.x+1][s.y-1] != ‘#‘ && mark[s.x+1][s.y][1] == false && mark[s.x+1][s.y-1][3] == false)
            {
                t.ty = 1;
                t.x = s.x+1;
                t.y = s.y;
                t.ans = s.ans+1;

                mark[s.x+1][s.y][1] = true ;
                mark[s.x+1][s.y-1][3] = true ;

                q.push(t);
            }

            if(s.y-1 >= 1 && s.x-1 >= 1 && Map[s.x-1][s.y] != ‘#‘ && Map[s.x-1][s.y-1] != ‘#‘ && mark[s.x-1][s.y][1] == false && mark[s.x-1][s.y-1][3] == false)
            {
                t.ty = 1;
                t.x = s.x-1;
                t.y = s.y;
                t.ans = s.ans+1;

                mark[s.x-1][s.y][1] = true ;
                mark[s.x-1][s.y-1][3] = true ;

                q.push(t);
            }
        }
        else if(s.ty == 2)
        {
            if(s.x-1 >= 1 && Map[s.x-1][s.y] != ‘#‘ && Map[s.x-1][s.y] != ‘E‘ && mark[s.x-1][s.y][4] == false)
            {
                t.ty = 4;
                t.x = s.x-1;
                t.y = s.y;
                t.ans = s.ans + 1;

                mark[s.x-1][s.y][4] = true;

                q.push(t);
            }

            if(s.x+2 <= n && Map[s.x+2][s.y] != ‘#‘ && Map[s.x+2][s.y] != ‘E‘ && mark[s.x+2][s.y][4] == false)
            {
                t.ty = 4;
                t.x = s.x+2;
                t.y = s.y;
                t.ans = s.ans+1;

                mark[s.x+2][s.y][4] = true;

                q.push(t);

            }

            if(s.y+1 <= m && s.x+1 <= n && Map[s.x][s.y+1] != ‘#‘ && Map[s.x+1][s.y+1] != ‘#‘ && mark[s.x][s.y+1][2] == false && mark[s.x+1][s.y+1][0] == false)
            {
                t.ty = 2;
                t.x = s.x;
                t.y = s.y+1;
                t.ans = s.ans+1;

                mark[s.x][s.y+1][2] = true ;
                mark[s.x+1][s.y+1][0] = true ;

                q.push(t);
            }

            if(s.y-1 >= 1 && s.x+1 <= n && Map[s.x][s.y-1] != ‘#‘ && Map[s.x+1][s.y-1] != ‘#‘ && mark[s.x][s.y-1][2] == false && mark[s.x+1][s.y-1][0] == false)
            {
                t.ty = 2;
                t.x = s.x;
                t.y = s.y-1;
                t.ans = s.ans+1;

                mark[s.x][s.y-1][2] = true ;
                mark[s.x+1][s.y-1][0] = true ;

                q.push(t);
            }
        }
        else if(s.ty == 3)
        {
            if(s.y-1 >= 1 && Map[s.x][s.y-1] != ‘#‘ && Map[s.x][s.y-1] != ‘E‘ && mark[s.x][s.y-1][4] == false)
            {
                t.ty = 4;
                t.x = s.x;
                t.y = s.y-1;
                t.ans = s.ans + 1;

                mark[s.x][s.y-1][4] = true;

                q.push(t);
            }

            if(s.y+2 <= m && Map[s.x][s.y+2] != ‘#‘ && Map[s.x][s.y+2] != ‘E‘ && mark[s.x][s.y+2][4] == false)
            {
                t.ty = 4;
                t.x = s.x;
                t.y = s.y+2;
                t.ans = s.ans+1;

                mark[s.x][s.y+2][4] = true;

                q.push(t);

            }

            if(s.y+1 <= m && s.x+1 <= n && Map[s.x+1][s.y] != ‘#‘ && Map[s.x+1][s.y+1] != ‘#‘ && mark[s.x+1][s.y][3] == false && mark[s.x+1][s.y+1][1] == false)
            {
                t.ty = 3;
                t.x = s.x+1;
                t.y = s.y;
                t.ans = s.ans+1;

                mark[s.x+1][s.y][3] = true ;
                mark[s.x+1][s.y+1][1] = true ;

                q.push(t);
            }

            if(s.y+1 <= m && s.x-1 >= 1 && Map[s.x-1][s.y] != ‘#‘ && Map[s.x-1][s.y+1] != ‘#‘ && mark[s.x-1][s.y][3] == false && mark[s.x-1][s.y+1][1] == false)
            {
                t.ty = 3;
                t.x = s.x-1;
                t.y = s.y;
                t.ans = s.ans+1;

                mark[s.x-1][s.y][3] = true ;
                mark[s.x-1][s.y+1][1] = true ;

                q.push(t);
            }
        }
        else if(s.ty == 4)
        {
            if(s.x-2 >= 1 && Map[s.x-1][s.y] != ‘#‘ && Map[s.x-2][s.y] != ‘#‘ && mark[s.x-1][s.y][0] == false && mark[s.x-2][s.y][2] == false)
            {
                t.ty = 0;
                t.x = s.x-1;
                t.y = s.y;
                t.ans = s.ans+1;

                mark[s.x-1][s.y][0] = true;
                mark[s.x-2][s.y][2] = true;

                q.push(t);
            }

            if(s.x+2 <= n && Map[s.x+1][s.y] != ‘#‘ && Map[s.x+2][s.y] != ‘#‘ && mark[s.x+1][s.y][2] == false && mark[s.x+2][s.y][0] == false)
            {
                t.ty = 2;
                t.x = s.x+1;
                t.y = s.y;
                t.ans = s.ans+1;

                mark[s.x+1][s.y][2] = true;
                mark[s.x+2][s.y][0] = true;

                q.push(t);
            }

            if(s.y-2 >= 1 && Map[s.x][s.y-1] != ‘#‘ && Map[s.x][s.y-2] != ‘#‘ && mark[s.x][s.y-1][1] == false && mark[s.x][s.y-2][3] == false)
            {
                t.ty = 1;
                t.x = s.x;
                t.y = s.y-1;
                t.ans = s.ans+1;

                mark[s.x][s.y-1][1] = true;
                mark[s.x][s.y-2][3] = true;

                q.push(t);
            }

            if(s.y+2 <= m && Map[s.x][s.y+1] != ‘#‘ && Map[s.x][s.y+2] != ‘#‘ && mark[s.x][s.y+1][3] == false && mark[s.x][s.y+2][1] == false)
            {
                t.ty = 3;
                t.x = s.x;
                t.y = s.y+1;
                t.ans = s.ans+1;

                mark[s.x][s.y+1][3] = true;
                mark[s.x][s.y+2][1] = true;

                q.push(t);
            }
        }
    }
    cout<<"Impossible"<<endl;
}

int main()
{
    int i,n,m;

    while(scanf("%d %d",&n,&m) && (n||m))
    {

        for(i = 1;i <= n; ++i)
        {
            scanf("%*c%s",Map[i]+1);
        }

        bfs(n,m);
    }
    return 0;
}


POJ 3322 Bloxorz I 三维BFS

上一篇:SGU118 数学题 Math


下一篇:Windows XP系统搜索故障及处理办法点点通