博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
FZU - 1688 Binary land
阅读量:5839 次
发布时间:2019-06-18

本文共 3646 字,大约阅读时间需要 12 分钟。

 Problem 1688 Binary land

Accept: 72    Submit: 171

Time Limit: 1000 mSec    Memory Limit : 32768 KB

 Problem Description

 

Daxia liked a game named “binary land” (双企鹅,一款家机游戏) when he was a child. Now, we will solve the problem about this game.You are in control of two penguins – Gurin (blue) and Malon (pink). Each level is divided more or less in half, with Gurin on the right and Malon on the left. They move the same way in vertical direction, but they move in a mirror image in horizontal direction. That is if you press right, Gurin moves right but Malon moves left, and if you press left, Gurin moves left but Malon moves right. You can press up, down, left and right. If an operation leads the penguin to the wall, the penguin will stay in the original place. Every operation is counted one step.

 

These two penguins are in love and so your task is to open the cage with the heart on the top of the screen. This cage can be opened only if the penguins are on both sides of it as the following picture (either Gurin on the right or on the left is OK). Now ask you to compute the least steps to achieve it.

 

 Input

Input contains several cases. Each case includes ten lines, each line has fifteen characters. The eighth column is always beginning with one cage with the heart and following nine walls. The wall can't be across but the cage with the heart can be across. The two penguins can be across each other, too. There is a blank line between two cases. The meaning of the characters is:
  • "." is used for road.
  • "#" is used for wall.
  • "G" is used for Gurin (only one, and in the tenth line and ninth column).
  • "M" is used for Malon (only one, and in the tenth line and seventh column).
  • "C" is used for cage with the heart (only one, and in the first line and eighth column).

 Output

Ououtput a single line for each of the case. This line should contain either "Case i: d" or "Case i: They can’t break open the cage!", where i is the case number (counting from 1) and d is the minimum steps needed to use.

 Sample Input

.......C..............#..............#..............#..............#..............#..............#..............#..............#.............M#G.............C........###.###.###.####.#.#.###.#.#........#........#####.#.#####........#.......##.#.#.#.#.#.##.......#........#############.......M#G............#C..............#..............#..............#..............#..............#..............#..............#..............#.............M#G......

 Sample Output

Case 1: 9
Case 2: 30
Case 3: They can't break open the cage!
 
分析 
  裸的bfs问题。同时处理两个点的行走就好。比赛时想到了但没有去码,后悔莫及啊,太年轻。
 
#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long LL;const int maxn = 1e4+5;const int mod = 772002+233;typedef pair
pii;#define X first#define Y second#define pb push_back#define mp make_pair#define ms(a,b) memset(a,b,sizeof(a))int d[11][17][11][17];char g[11][17];pii C,G,M;queue
> q;int dx[]={ 1,0,-1,0};int dy[]={ 0,1,0,-1};const int inf = 0x3f3f3f3f;int main(){ //cout<
9||a.Y<0||a.Y>14) a=tg; if(b.X<0||b.X>9||b.Y<0||b.Y>14) b=tm; if(g[a.X][a.Y]=='#') a=tg; if(g[b.X][b.Y]=='#') b=tm; if(d[a.X][a.Y][b.X][b.Y]!=inf) continue; d[a.X][a.Y][b.X][b.Y]= d[tg.X][tg.Y][tm.X][tm.Y]+1; q.push(mp(a,b)); } }// int ans=min(d[C.X][C.Y+1][C.X][C.Y-1],d[C.X][C.Y-1][C.X][C.Y+1]); int ans=d[C.X][C.Y+1][C.X][C.Y-1]; printf("Case %d: ",cas++); if(ans==inf){ puts("They can't break open the cage!"); }else cout<
<

 

 

转载于:https://www.cnblogs.com/fht-litost/p/8537597.html

你可能感兴趣的文章
除了 iOS 和 Android,世界第三大移动系统是什么?
查看>>
35.7. FAQ
查看>>
winfrom GDI知识
查看>>
【故障-ORACLE】rdbms ipc message timeout解释
查看>>
System.Threading.Tasks.Task 任务引起的IIS应用程序池崩溃
查看>>
解剖SQLSERVER 第十二篇 OrcaMDF 行压缩支持(译)
查看>>
深搜算法实例:老鼠走迷宫(一)
查看>>
VMWare网络设置的3中方式(转)
查看>>
支付这条线上 谁在赚钱谁在哭?
查看>>
机器学习之朴素贝叶斯分类
查看>>
亚信安全参加第六届全国等保技术大会 态势感知助力“等保2.0”落地
查看>>
【设计模式系列】--抽象工厂
查看>>
JqueryValidate 动态添加验证
查看>>
HTAP数据库 PostgreSQL 场景与性能测试之 36 - (OLTP+OLAP) 不含索引单表批量写入
查看>>
让程序使用自带的字体2
查看>>
Configuring Java CAPS for SSL Support - Index
查看>>
“增长黑客”与LBS
查看>>
虚拟化和云计算路向何方?
查看>>
户外抓绒衣的选择要点
查看>>
PHP设计模式——中介者模式
查看>>