아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Move One Coin

시간 제한2초메모리 제한1024 MB

요약
주어진 소스 패턴과 목표 패턴이 90도 회전과 평행 이동으로 일치하도록, 동전 하나를 옮겨 두 패턴을 맞추는 이동을 찾는다.
난이도

보통10점 중 6점

유형
기하, 구현, 해시맵, 완전 탐색
정답자
아직 제출이 없습니다

문제

Some coins are placed on grid points on a two-dimensional plane. No two coins are stacked on the same point. Let’s call this placement of coins the source pattern. Another placement of the same number of coins, called the target pattern, is also given.

The source pattern does not match the target pattern, but by moving exactly one coin in the source pattern to an empty grid point, the resulting new pattern matches the target pattern. Your task is to find out such a coin move.

Here, two patterns are said to match if one pattern is obtained from the other by applying some number of 90-degree rotations on the plane and a parallel displacement if necessary, but without mirroring. For example, in the source pattern on the left of Figure D.1, by moving the coin at (1,0)(1, 0) to (3,1)(3, 1), we obtain the pattern on the right that matches the target pattern shown in Figure D.2.

Figure D.1. Source pattern and a move

Figure D.2. Target Pattern

입력

The input consists of a single test case of the following format.

hh ww

p_0,0p\_{0,0} ⋯\cdots p_0,w−1p\_{0,w-1}

⋮\vdots

p_h−1,0p\_{h-1,0} ⋯\cdots p_h−1,w−1p\_{h-1,w-1}

HH WW

P_0,0P\_{0,0} ⋯\cdots P_0,W−1P\_{0,W-1}

⋮\vdots

P_H−1,0P\_{H-1,0} ⋯\cdots P_H−1,W−1P\_{H-1,W-1}

The first line consists of two integers hh and ww, both between 11 and 500500, inclusive. hh is the height and ww is the width of the source pattern description. The next hh lines each consisting of ww characters describe the source pattern. The character p_y,xp\_{y,x} being ‘o’ means that a coin is placed at (x,y)(x, y), while ‘x’ means no coin is there.

The following lines with integers HH and WW, and characters P_y,xP\_{y,x} describe the target pattern in the same way.

출력

If the answer is to move the coin at (x_0,y_0)(x\_0, y\_0) to (x_1,y_1)(x\_1, y\_1), print x_0x\_0 and y_0y\_0 in this order separated by a space character in the first line, and print x_1x\_1 and y_1y\_1 in this order separated by a space character in the second line.

It is ensured there is at least one move that satisfies the requirement. When multiple solutions exist, print any one of them.

Note that 0≤x_0<w0 ≤ x\_0 < w and 0≤y_0<h0 ≤ y\_0 < h always hold but x_1x\_1 and/or y_1y\_1 can be out of these ranges.

예제2

  1. 예제 1

    입력
    2 3
    xox
    ooo
    4 2
    ox
    ox
    ox
    ox
    
    예상 출력
    1 0
    3 1
    
  2. 예제 2

    입력
    3 3
    xox
    oxo
    xox
    4 4
    oxxx
    xxox
    xoxo
    xxxx
    
    예상 출력
    1 2
    -1 -1