FZU

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<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include <queue>
using namespace std;
typedef long long LL;
const int maxn = 1e4+5;
const int mod = 772002+233;
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[11][17][11][17];
char g[11][17];
pii C,G,M;
queue<pair<pii,pii> > q;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
const int inf = 0x3f3f3f3f;
int main(){
       //cout<<inf;
    int cas=1;
    while(~scanf("%s",g[0])){
        for(int i=1;i<10;i++) scanf("%s",g[i]);
        for(int i=0;i<10;i++){
            for(int j=0;j<15;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]=0;
        q.push(mp(G,M));
        while(!q.empty()){
            pii tg=q.front().X;
            pii tm=q.front().Y;
            q.pop();
            for(int i=0;i<4;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<0||a.X>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<<ans<<endl;
    }

    return 0;
}