`
阿尔萨斯
  • 浏览: 4108347 次
社区版块
存档分类
最新评论

POJ 3322 Bloxorz I(BFS:求迷宫最短路径)

 
阅读更多

POJ 3322 Bloxorz I(BFS:求迷宫最短路径)

http://poj.org/problem?id=3322

题意:有一个R*C的网格,网格中有3种格子:正常格子,脆弱格子以及空格子.现在给你一个1*2立方体的初始位置,要你求出将该立方体移动到终点所需要的最小步数.


分析:其实和一般的BFS求最短路径没本质区别,就是状态设计和移动可能复杂点.

我们令1*2木块的状态为:

struct node

{

int t;

int r1,c1;

int r2,c2;

}; 这里注意 r1<=r2且c1<=c2,保证r1和c1是左上角那个格子的坐标.

t表示木块当前的状态,为1,2或3.

当t==1时,表示木块此时是竖直的.所以(r1,c1)==(r2,c2).此时如果木块分别向上下左右4个方向运动,它们的r1,c1,r2,c2的增量为:

{-1,0,0,0},{0,0,1,0},{0,-1,0,0},{0,0,0,1}.另外两个状态的移动情况看代码.

求出了移动向量,接下来就是算出新的nr1,nc1,nr2,nc2了.然后验证新的状态是否满足合法.合法的话且之前没有出现该状态,则可以进行状态转移.

由于r1和c1记录的是左上角的坐标,所以我们只需要一个t和r1和c1就可以推出r2和c2的坐标.所以我们只需要vis[t][r1][c1]来判重即可.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=500*500*3+100;
const int maxr=505;
const int maxc=505;
int move[3][4][4]={  //错误1 这里t=2,3时的坐标转移写错了, 结果发现这里t=1也写错了,悲剧
                   {{-2,0,-1,0},{1,0,2,0},{0,-2,0,-1},{0,1,0,2}},  //t=1时,上下左右
                   {{-1,0,-1,0},{1,0,1,0},{0,-1,0,-2},{0,2,0,1}},//t=2时,沿x轴(即列增涨方向)水平放
                   {{-1,0,-2,0},{2,0,1,0},{0,-1,0,-1},{0,1,0,1}} //t=3时,沿y轴水平放
                   };
struct node
{
    int t;     // t=1,2,3,分别表示 竖放,沿x轴平放,沿y轴平放
    int r1,c1; //r1<=r2且c1<=c2
    int r2,c2;
    int dist;
    node(){}
    node(int t,int r1,int c1,int r2,int c2,int d):t(t),r1(r1),c1(c1),r2(r2),c2(c2),dist(d){}
}Q[maxn];//BFS队列
int vis[4][maxr][maxc];
int R,C;
char map[maxr][maxc];
bool check(int i)
{
    int t=Q[i].t,r1=Q[i].r1,c1=Q[i].c1,r2=Q[i].r2,c2=Q[i].c2;
    if(!vis[t][r1][c1] && r1>=0 && r1<R&&c1>=0&&c1<C&&r2>=0&&r2<R&&c2>=0&&c2<C)  //错误2 把<C 写成了<R
        if(t==1 && (map[r1][c1]=='X' || map[r1][c1]=='O'||map[r1][c1]=='.') )//竖放
            return true;
        else if(t!=1 && map[r1][c1]!='#' && map[r2][c2]!='#')
            return true;
    return false;
}
int BFS()
{
    int front=0,tail=1;
    memset(vis,0,sizeof(vis));
    vis[Q[0].t][Q[0].r1][Q[0].c1]=1;
    while(front<tail)
    {
        for(int d=0;d<4;d++)
        {
            Q[tail]=Q[front];      //确定新状态
            Q[tail].r1=Q[front].r1 + move[Q[front].t-1][d][0];  //错误3,这里Q[front].t 开始没减1
            Q[tail].c1=Q[front].c1 + move[Q[front].t-1][d][1];
            Q[tail].r2=Q[front].r2 + move[Q[front].t-1][d][2];
            Q[tail].c2=Q[front].c2 + move[Q[front].t-1][d][3];
            Q[tail].dist=1 + Q[front].dist;
            if(Q[tail].r1==Q[tail].r2 && Q[tail].c1==Q[tail].c2)
                Q[tail].t=1;
            else Q[tail].t= (Q[tail].r1==Q[tail].r2)?2:3;

            if(check(tail))//第tail个状态合法且没出现过
            {
                vis[Q[tail].t][Q[tail].r1][Q[tail].c1]=1;
                if(Q[tail].t==1 && map[Q[tail].r1][Q[tail].c1]=='O') return Q[tail].dist;
                tail++;
            }
        }
        front++;
    }
    return -1;
}
int main()
{
    while(scanf("%d%d",&R,&C)==2&&R&&C)
    {
        for(int i=0;i<R;i++)
            scanf("%s",map[i]);

        int t,r1,c1,r2,c2,cnt=0;//cnt用来记录初始的时候map有几个'X'
        for(int i=0;i<R;i++)  //设置Q[0],即初始木块的状态
        for(int j=0;j<C;j++)if(map[i][j]=='X')
        {
            if(++cnt==1) r1=i,c1=j;
            else r2=i,c2=j;
        }
        if(cnt==1) Q[0]=node(1,r1,c1,r1,c1,0);//初始竖放
        else
        {
            //if(r1>r2){swap(r1,r2); swap(c1,c2);} //其实这句可省,按我们从上到下的扫描顺序,r1肯定是较小的那个
            t= (r1==r2)?2:3;
            Q[0]=node(t,r1,c1,r2,c2,0);
        }

        //printf("%d %d %d %d %d\n",Q[0].t,Q[0].r1,Q[0].c1,Q[0].r2,Q[0].c2);
        int ans=BFS();
        if(ans==-1) printf("Impossible\n");
        else printf("%d\n",ans);
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics