시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB10711912.857%

문제

종혁이와 재홍이는 종이 레이싱을 즐긴다. 트랙은 종이를 정사각형으로 나눈 것이다. 각 칸은 도로 또는 장애물이다. 두 개의 도로는 시작과 끝으로 표시되어져 있다. 이 게임의 목표는 시작에서 차를 출발시켜서 끝으로 최대한 빨리 이동시키는 것이다.

이 게임에서 차는 점 하나로 표시된다. 움직임은 각 턴으로 움직인다. 각 턴의 시작에 차는 어떤 칸의 중심에 있다. 그리고 각 턴의 움직임은 다른 칸의 중심으로 이동하는 것이다. 차의 속도는 정수 좌표를 가진 벡터이다. 각 턴은 다음과 같이 이루어져 있다.

  1. 이번 턴이 시작하기 바로 전에 차의 속도를 바꿀 수 있는데, 속도의 각 좌표를 1씩 증가시키거나, 1씩 감소시키거나, 그대로 놔둘 수 있다. (두 좌표를 같이 증가시키거나, 감소시켜야 하는 것은 아니다. 서로 다른 연산을 할 수 있다.)
  2. 차를 움직인다. 만약 차가 (r, c)에 있고, 차의 속도가 (vr, vc)라면, 차가 이동하는 새로운 좌표는 (r+vr, c+vc)이다. 차는 이전에 있던 칸의 중심과, 새로운 칸의 중심을 이은 직선을 따라 이동한다.

만약 차의 이동 경로가 끝이 쓰여 있는 도로를 지난다면, 게임은 즉시 끝이 나고, 그때 까지의 턴의 개수가 이동한 시간이 된다. 만약 차의 경로가 게임이 끝나기 전에 장애물을 지난다면, 차는 부수어지고, 게임을 끝마칠 수 없게 된다. (차는 장애물을 스칠 수 있다)

차는 종이를 벗어날 수 없다. (종이를 벗어나면 실격처리 된다)

만약 차가 이동하는 곳의 위치가 장애물이거나, 종이 밖이라고 해도, 그 전에 끝을 통과한다면, 게임은 성공적으로 끝난다.

종이의 모양과 vr, vc가 주어졌을 때, 게임을 끝내는데 드는 턴의 최솟값을 구하는 프로그램을 작성하시오. 만약 끝까지 가는 것이 불가능하다면 -1을 출력한다.

입력

첫째 줄에 N과 M이 주어진다. 둘째 줄부터 N개의 줄에 종이의 모양이 주어진다. ‘.’은 도로, ‘S’는 시작, ‘F’는 끝, ‘X’는 장애물이다. 마지막 줄에는 vr과 vc가 주어진다. N과 M은 50보다 작거나 같은 자연수이고, vr과 vc는 절댓값이 50보다 작거나 같은 정수이다. 종이에 S와 F는 항상 하나만 있다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

5 2
FX
X.
.X
X.
SX
1 0

예제 출력 1

8

예제 입력 2

1 19
S.................F
0 0

예제 출력 2

6

예제 입력 3

1 19
S.................F
0 8

예제 출력 3

2

예제 입력 4

4 4
S..X
X..X
XX.X
XXFX
50 50

예제 출력 4

1

예제 입력 5

1 19
S.......X.........F
0 0

예제 출력 5

-1

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013