题意:地图上分别用‘.’表示硬地,‘#’表示禁地,‘E’表示易碎地面。你的任务操作一个1*1*2的长方体。长方体有两种状态分别为:立在地面上,躺在地面上。把长方体从入口移动到出口,求需要的最小步数。

原题链接:http://poj.org/problem?id=3322

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std; struct node{
int x;
int y;
int lie; //lie=0,代表竖着;lie=1,代表横着躺着;lie=2,代表垂直躺着
}; char map[][];
int r,c;//r表示地图的行数,c表示地图的列数
node start,end; //记录起点和终点的状态
int dx[]={-,,,};//表示左右方向的移动
int dy[]={,,,-};//表示上下方向的移动
int dis[][][];//记录起点走到x,y时候,状态为lie的路径长度 void init()
{
for(int i=;i<=r;i++)
{
for(int j=;j<=c;j++)
{
for(int k=;k<;k++)
{
dis[i][j][k]=-;
}
}
}
} bool judge(int x,int y)
{
if(x<=r&&x>=&&y<=c&&y>=)
{
return true;
}
return false;
} bool judge_stay(node n)//判断一个长方体呆着是否合理
{
if(!judge(n.x,n.y))
return ;
if(map[n.x][n.y]=='#')
return ;
if(n.lie==&&map[n.x][n.y]!='.')
return ;
if(n.lie==&&(map[n.x][n.y+]=='#'))
return ;
if(n.lie==&&(map[n.x+][n.y]=='#'))
return ;
return ;
}
/*
int dx_lie0[4]={0,0,-2,1};//lie=0的时候,向四个方向运动时,x的变化。 左右上下
int dy_lie0[4]={-2,1,0,0};//lie=0的时候,向四个方向运动时,y的变化。
int dx_lie1[4]={0,0,-1,1};
int dy_lie1[4]={-1,2,0,0};
int dx_lie2[4]={0,0,-1,2};
int dy_lie2[4]={-1,1,0,0};
*/ int dx_lie[][]={,,-,,,,-,,,,-,};
int dy_lie[][]={-,,,,-,,,,-,,,};
int lie[][]={,,,,,,,,,,,};//lie[i][j]表示状态为i的时候,向j方向反转后,lie的状态 int bfs()
{
queue<node>q;
while(!q.empty())
{
q.pop();
}
q.push(start);
dis[start.x][start.y][start.lie]=;
while(!q.empty())
{
node t=q.front();
q.pop();
for(int k=;k<;k++)
{
node next;
next.x=t.x+dx_lie[t.lie][k];
next.y=t.y+dy_lie[t.lie][k];
next.lie=lie[t.lie][k];
if(judge_stay(next))
{
if(dis[next.x][next.y][next.lie]==-)
{
//cout<<t.x<<' '<<t.y<<' '<<t.lie<<endl;
//cout<<"x"<<next.x<<endl;
//cout<<"y"<<next.y<<endl;
//cout<<"lie"<<next.lie<<endl; q.push(next);
dis[next.x][next.y][next.lie]=dis[t.x][t.y][t.lie]+;
//cout<<endl<<"x"<<next.x<<" y"<<next.y<<" lie"<<next.lie<<" dis"<<dis[next.x][next.y][next.lie];
//cout<<endl<<endl;
if(next.x==end.x&&next.y==end.y&&next.lie==end.lie)
{
return dis[next.x][next.y][next.lie];
}
}
}
}
}
return -;
} void fun_st_ed() //处理起点和终点
{
for(int i=;i<=r;i++)
{
for(int j=;j<=c;j++)
{
if(map[i][j]=='O')
{
end.x=i;
end.y=j;
end.lie=;
map[i][j]='.';
}
if(map[i][j]=='X')
{
for(int k=;k<;k++)
{
int next_x=i+dx[k];
int next_y=j+dy[k];
if(judge(next_x,next_y)&&map[next_x][next_y]=='X')
{
start.x=min(i,next_x);
start.y=min(j,next_y);
start.lie=k<?:;//k<2的时候说明是上下有连着的X,k>2说明左右有连着的X;
map[i][j]='.';
map[next_x][next_y]='.';
}
}
}
if(map[i][j]=='X')//说明周围四个点当中没有X。
{
//cout<<"i"<<i<<"j"<<j<<endl;
start.x=i;
start.y=j;
start.lie=;
map[i][j]='.';
}
}
}
} int main()
{
while(cin>>r>>c)
{
if(r==&&c==)
{
break;
}
memset(map,,sizeof(map));
for(int i=;i<=r;i++)
{
//for(int j=1;j<=c;j++)
//{
//cin>>map[i][j];
scanf("%s",map[i]+);
//}
//getchar();
}
init();
fun_st_ed();
//cout<<start.x<<start.y<<start.lie<<endl;
int ans=bfs();
if(ans==-)
{
cout<<"Impossible"<<endl;
}
else
{
cout<<ans<<endl;
}
}
return ;
} /*
7 7
#######
#...X##
#..##O#
#....E#
#....E#
#.....#
#######
*/

解题思路:用bfs求最短路径。用数组表示前状态和后状态的关系。用dis数组记录最短路径的长度。

最新文章

  1. 【转】Nginx中upstream有以下几种方式:
  2. ngrok反向代理
  3. hdu 2665 Kth number(划分树模板)
  4. python 单元测试
  5. KEIL C51中的_at_关键字
  6. xls 打乱序列 -和给拼接字符串加上双引号
  7. ueditorUE 去掉本地保存成功的提示框!
  8. C++关于运算符重载知识点
  9. NetCore 控制台读取配置文件
  10. Bug 14143011 : ORA-19606: CANNOT COPY OR RESTORE TO SNAPSHOT CONTROL FILE
  11. Linux基础命令---文本过滤coi
  12. C# if else 使物体在X轴循环移动
  13. pandas.read_csv 参数 index_col=0
  14. php 对象 调用静态方法
  15. Form.ShowDialog(this)
  16. C# Socket服务端与客户端通信(包含大文件的断点传输)
  17. Nginx+tomcat+redis集群共享session实现负载均衡
  18. POJ 2486 Apple Tree [树状DP]
  19. umount 卸载 无响应的 NFS 文件系统
  20. stl之multiset容器的应用

热门文章

  1. Hadoop| YARN| 计数器| 压缩| 调优
  2. MyCat-简介
  3. Imcash平台测评报告
  4. (二)文档请求不同源之window.postMessage跨域
  5. 杭电1532----Drainage Ditches『最大流』
  6. Django——微信消息推送
  7. django 小东小西
  8. 【IT小常识】如何将IE手动升级或降级
  9. vue调用Moment显示时间
  10. (98)Wangdao.com_第三十天_拖拉事件