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
- "." 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
Sample Input
.......C.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
......M#G...... .......C.......
.###.###.###.##
##.#.#.###.#.#.
.......#.......
.#####.#.#####.
.......#.......
##.#.#.#.#.#.##
.......#.......
.#############.
......M#G...... ......#C.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
.......#.......
......M#G......
Sample Output
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include <queue>
using namespace std;
typedef long long LL;
const int maxn = 1e4+;
const int mod = +;
typedef pair<int,int> 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[][][][];
char g[][];
pii C,G,M;
queue<pair<pii,pii> > q;
int dx[]={,,-,};
int dy[]={,,,-};
const int inf = 0x3f3f3f3f;
int main(){
//cout<<inf;
int cas=;
while(~scanf("%s",g[])){
for(int i=;i<;i++) scanf("%s",g[i]);
for(int i=;i<;i++){
for(int j=;j<;j++){
if(g[i][j]=='C') C=mp(i,j);
else if(g[i][j]=='G') G=mp(i,j);
else if(g[i][j]=='M') M=mp(i,j);
}
}
// for(int i=0;i<10;i++) puts(g[i]); ms(d,inf);
d[G.X][G.Y][M.X][M.Y]=;
q.push(mp(G,M));
while(!q.empty()){
pii tg=q.front().X;
pii tm=q.front().Y;
q.pop();
for(int i=;i<;i++){
pii a=tg,b=tm;
a.X+=dx[i]; a.Y+=dy[i];
b.X+=dx[i]; b.Y-=dy[i];
if(a.X<||a.X>||a.Y<||a.Y>) a=tg;
if(b.X<||b.X>||b.Y<||b.Y>) 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]+;
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+][C.X][C.Y-];
printf("Case %d: ",cas++);
if(ans==inf){
puts("They can't break open the cage!");
}else cout<<ans<<endl;
} return ;
}