Security & Hacking

이러고있을때가 아닌데... 죽일놈의 호기심;;;
웹서핑하다가.. 구글 코드잼이란걸 알게 되었는데 연습문제 해석 및 풀이 하는데 만만치가 않았다.;;
그래서 마지막문제의 난이도를 살펴보았다.

Problem

 

PortalTM is a first-person puzzle/platform game developed and published by Valve Software. The idea of the game was to create two portals on walls and then jump through one portal and come out the other. This problem has a similar idea but it does not assume you have played Portal.

 

For this problem you find yourself in a R by C grid. Additionally there is a delicious cake somewhere else in the grid. You're very hungry and wish to arrive at the cake with as few moves as possible. You can move north, south, east or west to an empty cell. Additionally, you have the ability to create portals on walls.

 

To help you get to the cake you have a portal gun which can shoot two types of portals, a yellow portal and a blue portal. A portal is created by shooting your portal gun either north, south, east or west. This emits a ball of energy that creates a portal on the first wall it hits. Note that for this problem shooting the portal gun does not count as a move. If you fire your portal gun at the cake, the energy ball will go right through it.

 

After creating a yellow portal and a blue portal, you can move through the yellow portal to arrive at the blue portal or vice versa. Using these portals you may be able to reach the cake even faster! You can only use portals after you create both a yellow and a blue portal.

 

Consider the following grid:

Gray cells represent walls, white cells represent empty cells, and the red circle indicates your position.

 

Suppose you shoot a blue portal east. The portal is created on the first wall it hits, resulting in:

 

 

Now suppose you shoot a yellow portal south:

 

 

Next you move south once:

 

 

Now comes the interesting part. If you move south one more time you go through the yellow portal to the blue portal:

 

 

There can only be one yellow portal and one blue portal at any time. For example if you attempt to create a blue portal to the west the other blue portal will disappear:

A portal disappears only when another portal of the same color is fired.

 

Note that the portals are created on one side of the wall. If a wall has a portal on its east side you must move into the wall from the east to go through the portal. Otherwise you'll be moving into a wall, which is improbable.

 

Finally, you may not put two portals on top of each other. If you try to fire a portal at a side of a wall that already has a portal, the second portal will fail to form.

 

Given the maze, your initial position, and the cake's position, you want to find the minimum number of moves needed to reach the cake if it is possible. Remember that shooting the portal gun does not count as a move.

 

Input

 

The first line of input gives the number of cases, N. N test cases follow.

 

The first line of each test case will contain the integers R and C separated by a space. R lines follow containing C characters each, representing the map:

 

. indicates an empty cell;

# indicates a wall;

O indicates your starting position; and

X indicates the cake's position.

There will be exactly one O and one X character per case.

 

Cells outside of the grid are all walls and you may use them to create portals.

 

Output

 

For each test case you should output one line containing "Case #X: Y" (quotes for clarity) where X is the number of the test case and Y is the minimum number of moves needed to reach the cake or "THE CAKE IS A LIE" (quotes for clarity) if the cake cannot be reached.

 

Limits

 

Small dataset

 

N = 200

1 <= R, C <= 8

 

Large dataset

 

N = 50

1 <= R, C <= 15

 

Sample

Input

3

4 7

.O..##.

.#.....

.#.####

.#...X.

5 5

O....

.....

.....

.....

....X

1 3

O#X

Output

Case #1: 4

Case #2: 2

Case #3: THE CAKE IS A LIE

Here is the sequence of moves for the first case (note that shooting the portal gun does not count as a move):

 

Move one step east.

Shoot a blue portal north.

Shoot a yellow portal south.

Move one step north through the blue portal.

Shoot a blue portal east.

Move one step south through the yellow portal.

Move one step west.

Eat your delicious and moist cake.

 

PortalTM is a trademark of Valve Inc. Valve Inc. does not endorse and has no involvement with Google Code Jam.

------->>>>>풀이 in Korean<<<<<<-----------
우선 미로찾는 알고리즘을 간단히 생각해 보았다.
이름하여 프로브 알고리즘.

전제:프로브는 자기가 지나온 길의 중요포인트(시작,끝,코너) 및 전체 코너의 수와 전체이동거리를 기억한다. 자기자신을 무한히 복사할 수 있다.(기억한거 포함) - (클래스로 구현하면 될듯)
맵을 읽어들인 배열이 있다.

미로찾기 알고리즘: 프로브알고리즘 by Carlo
스텝1:시작점에 프로브를 만든다.
스텝2:모든프로브는 새로운길이 2개이상일 경우 자기자신을 하나이상 복사하여 (어떠한방향으로)한칸 전진한다.
스텝3:모든프로브의 생과사를 점검한다. 
        1:충돌상황 점검: 생존의 우선순위 -- 적은전체거리>적은코너>컴퓨터저장상위랭크
        2:생존 프로브수: 0 이면 실패
        3:끝점에 도착한프로브? 있으면 성공
스텝4:Go to 스텝2

포탈사용 알고리즘: 포탈가속화알고리즘 by Carlo
전제:생존프로브는 중요 포인트, 전체 거리, 전체 코너수를 기억하고 있다.
      : Sum=0, N=0
스텝1:메모리에 기억하고있는 N,N+1번째 포인트 사의의 거리와 N,N+1번째 포인의 이동방향의 각각의 벽방향과의 거리의 합((N쪽벽과 N사이의거리)+ (N+1쪽벽과 N+1사이의 거리))과 비교하여 작은쪽으로 Sum에 더한다.
스텝2:if N+1== 전체코너+ 2 끝
스텝3:N++ Go to step1


------->>>>>Solution in English<<<<<-----------
First, I thought about sution of maze. 
I call Probe Algorithm;

PREMISE:Probe can remember the past points which are star,end,corners, the number of total distance and the number of total corners. It can make ones which are the same of its with memory 
there is an array of the maze map.

Maze Algorithm: Probe Algorithm by Carlo
Step1:Make the first probe at the start point.
Step2:All the probe make one more probes if there are two more new ways to go to the empty block and go one foot each direction.
Step3:Check all the probes to survive . 
        1:Check collision: Priority -- Shotest distance>Least Corner>High position in computer memory
        2:Check the number of probes : if n = 0 , failure
        3:Check the probe at the end point P if there is, success
Step4:Go to Step 2

Portal Algorithm: Simple Portal Algorithm by Carlo
PREMISE:there is a probe which has the informaion.
      : Sum=0, N=0
Step1:Sum += min(distance between N's point and N+1's point,  distance between N's point and opposit direction's wall + N+1's)
Step2:if N+1== total corner+ 2 : end
Step3:N++ Go to step1

--------------------->>>>>>>>>>>Analysis<<<<<<<<<<<<<<<<-----------------------------
 I'm worried about the overload of the probe algorithm
so, I had to estimate the algorithm

PREMISE: there is R*C maze.
               there are two points,like start and end points.
The number of probes: N is a positive number

1<N<2root2*min(R,C)

Speed: It must check all the probes per step.
            The number of the steps is R*C in simple thoutht

             There is no point in counting the number.
             Because probes and maps are limited 
        
 2root2*min(R,C)*R*C     = n   



-------------------->>>>>>>>>>>구현 Implement<<<<<<<<<<<<<----------------------------
구현은 나중에 시간이 있을 때 ^^ ( 변명인가);;
이번건 자바가 편할 것 같다..;;

----------------------------------------------------------------------------------------------
읽어 주셔서 감사 ^^ 잘못된것을 발견하면 지채없어.. 댓글 부탁..
추석이 어제 지났지만

 
----------------------------------------------------------------------------------------------