문제
부전자전(父傳子傳)이라는 사자성어가 있다. 쉽게 말하면 부모의 특징은 자식도 갖는다는 뜻이다.
재미있게도, 이를 영어에서는 “The apple doesn’t fall far from the tree”라고 표현한다.
직역하자면 사과는 사과나무에서 멀리에서 떨어지진 않는다는 것인데, 사과나무(부모)의 특징을 사과(자식)도 갖는다는 정도로 이해하면 될 것 같다.
그러나 우리가 누구인가. 바로 이과생이다.
이과생들은 속담의 속 뜻 같은 것은 관심이 없다.
우리는 진짜로 사과가 가까운 나무에서 떨어지는지 궁금할 뿐이다.
그래서 떨어진 사과와 가장 가까운 사과나무의 거리를 계산해주는 시뮬레이션 프로그램을 작성하기로 했다.
시뮬레이션 하는 벌판은 R×S의 2차원 격자칸으로 나타낼 수 있다.
사과나무가 하나라도 있는 곳은 ‘x’로, 없는 곳은 ‘.’로 나타내져 있다.
매년 한 개씩의 사과가 떨어지며, 그 위치는 매 해마다 주어진다.
사과가 떨어진 자리는 다음 해에 새로운 사과나무가 자란다(?!).
매 해마다 떨어지는 사과의 정보가 주어질 때, 가장 가까운 사과나무와의 거리 제곱을 계산하는 프로그램을 작성하라.
두 위치(x1, y1)과 (x2, y2)의 거리 제곱은 (x1- x2)2+ (y1 - y2)2이다.
[부분문제]
(부분문제 1)1 ≤ G ≤ 500일 때에 대해서 풀면 30점을 맞을 수 있으며,
(부분문제 2)1 ≤ G ≤ 100,000일 때에 대해서 풀면 100점을 맞을 수 있다.
입력
첫 줄에 R과 S이 주어진다.(1 ≤ R, S ≤ 500), 이는 2차원 격자칸의 크기이다.
다음 R행 S열에 걸쳐서 문자 ‘x’또는 ‘.’가 공백 없이 주어진다. 적어도 하나의 ‘x’가 존재한다.
다음 줄에 G가 주어지며, 시뮬레이션을 해야하는 총 년도의 수이다.
다음 G줄에 걸쳐서, 그 해에 사과가 떨어진 위치인 ri si가 공백을 사이에 두고 주어진다. 이는 해당 년도에 (ri, si)에 사과가 떨어졌음을 뜻한다.
출력
G개의 숫자를 출력하며, 각 줄에는 각 해마다 떨어진 사과와 가장 가까운 사과나무와의 거리 제곱을 출력한다.
예제 #1
3 3
x..
...
...
3
1 3
1 1
3 2
4
0
5
예제 #2
5 5
..x..
....x
.....
.....
.....
4
3 1
5 3
4 5
3 5
8
8
4
1
로그인해야 코드를 작성할 수 있어요.