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;
}
分享到:
相关推荐
问题:移动矩形方块,使其到达目标位置 算法:宽搜,因为方块为矩形,所以要处理好其落点问题
北大POJ1426-Find The Multiple【BFS+同余模】 解题报告+AC代码
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
poj 1062 昂贵的聘礼 代码 单源最短路径的Dijkstra算法
POJ上的DP分类: 容易: 1018, 1050, 1083, 1088, 1125, 1143, 1157, 1163, 1178, 1179, 1189, 1208, 1276, 1322, 1414, 1456, 1458, 1609, 1644, 1664, 1690, 1699, 1740(博弈), 1742, 1887, 1926(马尔科夫矩阵,求...
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
北大POJ初级题-数据结构:解题报告+AC代码
poj还是leetcode ProgrammingCompetionCareer 大学的竞赛生涯结束了,抽时间整理了一部分曾经在OJ刷过的题,还有一些找不到了,或者是因为杂物太多(除了代码以外还有题解的pdf、题目的测试数据等等),不想整理了就...
poj1125原创AC代码,用的是folyd算法,求出所有点之间的最短路径,再以此求出每个点到其他点的最长路径。。。
NULL 博文链接:https://128kj.iteye.com/blog/1754756
poj 2820 古代密码 http://poj.grids.cn/problem?id=2820 可直接运行
poj1002 source code input: The input will consist of one case. The first line of the input specifies the number of telephone numbers in the directory (up to 100,000) as a positive integer alone on ...
poj 5346题,四则运算表达式求值的实现,用栈和队列实现中缀转后缀后计算,含解题报告与源码
poj与leetcode
网上整理的一些poj刷题指南。 poj地址:http://poj.org
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj1691解题报告 题目来源:http://acm.pku.edu.cn/JudgeOnline/showproblem?problem_id=1691(POJ No.1691) 解法: 搜索
BFS POJ 3278 POJ 1426 POJ 3126 POJ 3414 POJ 2251 简单搜索技巧和剪枝 POJ 1010 :star: POJ 2362 POJ 1011(搜索+剪枝) POJ 1416 POJ 2676 POJ 1129:white_question_mark: 数据结构 串 POJ 1016 POJ 1035 POJ ...