Bloxorz I (poj 3322 水bfs)
Language:
Default
Bloxorz I
Description 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,
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 It guarantees that
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 Sample Output 10 Source
POJ Monthly--2007.08.05, Rainer
|
题意就不详细说了,去这里玩一下就知道了戳我玩游戏。还是非常好玩的~
思路:Move函数写得非常蛋疼,我是硬来的,一定要细心。
代码:
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#pragma comment (linker,"/STACK:102400000,102400000")
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define FRE(i,a,b) for(i = a; i <= b; i++)
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b) for(i = a; i < b; i++)
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v) memset ((t) , v, sizeof(t))
#define sf(n) scanf("%d", &n)
#define sff(a,b) scanf("%d %d", &a, &b)
#define sfff(a,b,c) scanf("%d %d %d", &a, &b, &c)
#define pf printf
#define DBG pf("Hi\n")
typedef long long ll;
using namespace std; #define INF 0x3f3f3f3f
#define mod 1000000009
const int maxn = 550;
const int MAXN = 2005;
const int MAXM = 200010;
const int N = 1005; struct Node
{
int state; //0表示立着 1表示横着 2表示竖着
int x1,y1,x2,y2;
int step;
}; int n,m;
int ex,ey;
char mp[maxn][maxn];
int dir[4][2]={0,-1,0,1,-1,0,1,0};
bool vis[3][maxn][maxn];
int pos[5]; bool isok(int x,int y)
{
if (x>=0&&x<n&&y>=0&&y<m&&mp[x][y]!='#') return true;
return false;
} bool Move(int x,int y,int d,Node &now)
{
if (now.state==0)
{
now.x1=x+dir[d][0]; now.y1=y+dir[d][1];
now.x2=x+2*dir[d][0]; now.y2=y+2*dir[d][1];
if (d==0||d==2) { //始终保持横着的左边一个为主块。竖着的上面一个为主块
swap(now.x1,now.x2);
swap(now.y1,now.y2);
}
if (d<2) now.state=1;
else now.state=2;
if (isok(now.x1,now.y1)&&isok(now.x2,now.y2)&&!vis[now.state][now.x1][now.y1])
return true;
}
else if (now.state==1)
{
if (d<2){
now.x1=x+dir[d][0]; now.y1=y+dir[d][1];
if (d==1) now.x1=now.x1+dir[d][0] , now.y1=now.y1+dir[d][1];
now.state=0;
if (isok(now.x1,now.y1)&&mp[now.x1][now.y1]!='E'&&!vis[now.state][now.x1][now.y1])
return true;
}
else
{
now.x1=x+dir[d][0]; now.y1=y+dir[d][1];
now.x2=now.x1; now.y2=now.y1+1;
if (isok(now.x1,now.y1)&&isok(now.x2,now.y2)&&!vis[now.state][now.x1][now.y1])
return true;
}
}
else
{
if (d>1){
now.x1=x+dir[d][0]; now.y1=y+dir[d][1];
if (d==3) now.x1=now.x1+dir[d][0] , now.y1=now.y1+dir[d][1];
now.state=0;
if (isok(now.x1,now.y1)&&mp[now.x1][now.y1]!='E'&&!vis[now.state][now.x1][now.y1])
return true;
}
else
{
now.x1=x+dir[d][0]; now.y1=y+dir[d][1];
now.x2=now.x1+1; now.y2=now.y1;
if (isok(now.x1,now.y1)&&isok(now.x2,now.y2)&&!vis[now.state][now.x1][now.y1])
return true;
}
}
return false;
} int bfs(int nn)
{
Node st,now;
memset(vis,false,sizeof(vis));
if (nn<3)
{
st.x1=pos[0];
st.y1=pos[1];
st.state=0;
}
else
{
st.x1=pos[0]; st.y1=pos[1];
st.x2=pos[2]; st.y2=pos[3];
if (st.x1==st.x2) st.state=1;
else st.state=2;
}
st.step=0;
vis[st.state][st.x1][st.y1]=true;
queue<Node>Q;
Q.push(st);
while (!Q.empty())
{
st=Q.front();Q.pop();
if (st.state==0&&st.x1==ex&&st.y1==ey)
return st.step;
// printf("\n");
// printf("=====================\n");
for (int i=0;i<4;i++)
{
now.state=st.state;
if (Move(st.x1,st.y1,i,now))
{
// printf("%d %d %d \n",now.state,now.x1,now.y1);
vis[now.state][now.x1][now.y1]=true;
now.step=st.step+1;
Q.push(now);
}
}
}
return -1;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("C:/Users/lyf/Desktop/IN.txt","r",stdin);
#endif
int i,j,num;
while (scanf("%d%d",&n,&m))
{
if (n==0&&m==0) break;
num=0;
for (i=0;i<n;i++)
{
scanf("%s",mp[i]);
for (j=0;j<m;j++)
{
if (mp[i][j]=='X')
{
pos[num++]=i;
pos[num++]=j;
}
if (mp[i][j]=='O')
{
ex=i;ey=j;
}
}
}
int ans=bfs(num);
if (ans==-1) printf("Impossible\n");
else printf("%d\n",ans);
}
return 0;
}
最新文章
- IO redirect
- visualssh 是一个可视化的ssh客户端
- EF架构~CodeFirst数据迁移与防数据库删除
- iocp-socket 服务(借鉴别人的,根据自己的需要改的)未完待续
- [jQuery]html(),text(),val()方法的区别
- zend studio 12.0 怎么汉化?
- codeforce 606C - Sorting Railway Cars
- 【原创】leetCodeOj --- Binary Tree Right Side View 解题报告
- NYOJ 25 A Famous Music Composer
- Java经典编程题50道之四十八
- webpack中hash与chunkhash区别和需要注意的问题
- RocketMQ源码 — 八、 RocketMQ消息重试
- springboot+activemq中引入重发机制
- 阿里云centos安装docker
- java中的静态代理和动态代理
- vscode setting.jsonxx
- ex_BSGS
- 随笔 js-----------------------------------------------------------------------------------------------------
- Vim 文件配置
- zabbix 配置SNMP监控
热门文章
- C# AES 加解密处理
- Java使用HttpURLConnection上传文件(转)
- (2016北京集训十)【xsy1528】azelso - 概率期望dp
- rescan-scsi-bus.sh linux扫盘 脚本
- 紫书 例题8-10 UVa 714 (二分答案)
- 【Henu ACM Round#24 A】k-String
- The Karplus-Strong Algorithm
- root用户无法切换到cdh的hive账号上
- Effective C++ 11-17
- HTML5实战与剖析之媒体元素(3、媒体元素的事件及方法)