寒假训练——搜索 E - Bloxorz I
Little Tom loves playing games. One day he downloads a little computer game called 'Bloxorz' which makes him excited. It's a game about rolling a box to a specific position on a special plane. Precisely, the plane, which is composed of several unit cells, is a rectangle shaped area. And the box, consisting of two perfectly aligned unit cube, may either lies down and occupies two neighbouring cells or stands up and occupies one single cell. One may move the box by picking one of the four edges of the box on the ground and rolling the box 90 degrees around that edge, which is counted as one move. There are three kinds of cells, rigid cells, easily broken cells and empty cells. A rigid cell can support full weight of the box, so it can be either one of the two cells that the box lies on or the cell that the box fully stands on. A easily broken cells can only support half the weight of the box, so it cannot be the only cell that the box stands on. An empty cell cannot support anything, so there cannot be any part of the box on that cell. The target of the game is to roll the box standing onto the only target cell on the plane with minimum moves.
The box stands on a single cell
The box lies on two neighbouring cells, horizontally
The box lies on two neighbouring cells, vertically
After Little Tom passes several stages of the game, he finds it much harder than he expected. So he turns to your help.
Input
Input contains multiple test cases. Each test case is one single stage of the game. It starts with two integers R and C(3 ≤ R, C ≤ 500) which stands for number of rows and columns of the plane. That follows the plane, which contains R lines and C characters for each line, with 'O' (Oh) for target cell, 'X' for initial position of the box, '.' for a rigid cell, '#' for a empty cell and 'E' for a easily broken cell. A test cases starts with two zeros ends the input.
It guarantees that
- There's only one 'O' in a plane.
- There's either one 'X' or neighbouring two 'X's in a plane.
- The first(and last) row(and column) must be '#'(empty cell).
- Cells covered by 'O' and 'X' are all rigid cells.
Output
For each test cases output one line with the minimum number of moves or "Impossible" (without quote) when there's no way to achieve the target cell.
Sample Input
7 7
#######
#..X###
#..##O#
#....E#
#....E#
#.....#
#######
0 0
Sample Output
10 题目:Bloxorz I
大意:(非博主翻译)
有两个相邻的X,理解为横躺。
思路:
就是一个bfs,不过不太一样,可以这么理解一下,如果X是正方体和平常迷宫问题有区别吗?这个题目只是X是长方体,
所以在id不同的位置,上下左右移动也不同。
X,若只有一个说明是竖放,两个则说明是延x轴或者y轴放。
X会上下左右移动,这时候就麻烦一点了,因为以前的vis数组是一个二维的直接存放位置即可,但是这个时候若是横放,则会占据
两个位置,不过不用急,很简单就可以想到的,用三维数组,以左上角为标准,和id一起构成判断标准,这样就不会重判了。
具体代码:
在main函数里面,先读取这个图像,然后根据X判断出横躺还是竖放,其次读取O的位置,这个为目标位置
在bfs函数里面,先将这个X的位置存放进去,然后进去搜索。
有一个check函数,就是把这个搜索之后的数读进去,判断,有没有到禁格里,有没有超出去,简单来说,就是是否合法。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
bool vis[5][505][505];
char a[505][505];
struct node
{
int id;
int r1,c1,r2,c2;
int step;
node(int id,int r1,int c1,int r2,int c2,int step):id(id),r1(r1),c1(c1),r2(r2),c2(c2),step(step){}
};
node ed=node(0,0,0,0,0,0),exa=node(0,0,0,0,0,0);
int to[3][4][4]={
{{-2,0,-1,0},{1,0,2,0},{0,1,0,2},{0,-2,0,-1}},
{{-1,0,-1,0},{1,0,1,0},{0,2,0,1},{0,-1,0,-2}},
{{-1,0,-2,0},{2,0,1,0},{0,1,0,1},{0,-1,0,-1}}
};
queue<node>que;
int cmp(int &x1,int &y1,int &x2,int &y2)//确定是竖放还是横躺
{
if(x1==x2&&y1==y2) return 1;
else if(x1==x2)
{
if(y1>y2) swap(y1,y2);
return 2;
}
else
{
if(x1>x2) swap(x1,x2);
return 3;
}
}
void check()//检查是否合法
{
if(a[exa.r1][exa.c1]=='#') return ;
if(a[exa.r2][exa.c2]=='#') return;
if(exa.id==1&&(a[exa.r1][exa.c1]=='E'||a[exa.r2][exa.c2]=='E')) return ;
if(vis[exa.id][exa.r1][exa.c1]) return ;
if(exa.r1<1||exa.r2<1||exa.r1>n||exa.r2>n||exa.c1<1||exa.c2<1||exa.c1>m||exa.c2>m) return ;
vis[exa.id][exa.r1][exa.c1]=1;
que.push(exa);
}
int bfs()//搜索,和普通一样的写法
{
while(!que.empty()) que.pop();
memset(vis,0,sizeof(vis));
vis[ed.id][ed.r1][ed.c1]=1;
que.push(ed);
while(!que.empty())
{
ed=que.front();
//printf("%d (%d,%d),(%d,%d)\n",ed.id,ed.r1,ed.c1,ed.r2,ed.c2);
que.pop();
if(ed.id==1&&a[ed.r1][ed.c2]=='O') return ed.step;
for(int i=0;i<4;i++)
{
exa.r1=ed.r1+to[ed.id-1][i][0];
exa.c1=ed.c1+to[ed.id-1][i][1];
exa.r2=ed.r2+to[ed.id-1][i][2];
exa.c2=ed.c2+to[ed.id-1][i][3];
exa.step=ed.step+1;
exa.id=cmp(exa.r1,exa.c1,exa.r2,exa.c2); check();
// printf("id=%d (%d,%d),(%d,%d) i=%d\n",exa.id,exa.r1,exa.c1,exa.r2,exa.c2,i);
}
}
return -1;
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF&&n+m)
{
int cnt=0,r1,c1,r2,c2;
for(int i=1;i<=n;i++)
{
scanf("%s",a[i]+1);
for(int j=1;j<=m;j++)
{
if(a[i][j]=='X')
{
cnt++;
if(cnt==1)
{
r1=r2=i;
c1=c2=j;
}
else
{
r2=i;
c2=j;
}
}
}
}
int t=cmp(r1,c1,r2,c2);
ed=node(t,r1,c1,r2,c2,0);
int exe=bfs();
if(exe==-1) printf("Impossible\n");
else printf("%d\n",exe);
}
return 0;
}
最新文章
- 进击的Python【第五章】:Python的高级应用(二)常用模块
- uva-10305
- 基于ASP.NET MVC的热插拔模块式开发框架(OrchardNoCMS)--瘦身计划
- 11g新特性-如何禁用自动统计信息收集作业
- .NET Core Runtime IDentifier (RID) catalog
- [Sciter系列] MFC下的Sciter&ndash;4.HTML与图片资源内置
- 验证Android用户输入日期
- 在终端里使用 Solarized 配色方案
- Linux中统计某个文件夹的大小
- Android的深度定制版阿里云os(Android的山寨)
- poj3358数论(欧拉定理)
- UNIX网络编程——揭开网络编程常见API的面纱【下】
- Hadoop入门
- 小程序上传wx.uploadFile - 小程序请假
- wmiprvse.exe cpu占用高怎么解决
- dts的pci模块中bus-range和ranges
- Unix IPC之Posix消息队列(3)
- Multipart polyline to single part lines
- 修复PHP支持的标准JSON数据格式
- 【bzoj4372】烁烁的游戏 动态点分治+线段树
热门文章
- [深度学习]理解RNN, GRU, LSTM 网络
- Struts2学习(一)————Struts2入门
- 基于Asp.Net Core的简单社区项目源代码开源
- csv文件格式说明
- 细说Redis(二)之 Redis的持久化
- [转]微擎load()文件加载器
- asp.net session mode 几种状态 (转)
- Extjs 项目中常用的小技巧,也许你用得着(3)
- 【Java并发编程】22、Exchanger源码解析(JDK1.7)
- java.lang.IllegalArgumentException Expected MultipartHttpServletRequest