4회 문제풀이 10 / ABC 201 D - Game in Momotetsu World

ABC 201 D - Game in Momotetsu World

【문제 개요】

H행 W열의 칸이 있으며 각 칸은 파란색칸 혹은 빨간색 칸입니다. 위에서 i번째, 왼쪽에서 j번째인 칸은 Aᵢⱼ이 +라면 파란칸, -라면 빨간칸이다.
최초 이 칸들의 가장 왼쪽 위의 칸에는 인형이 놓여있습니다. 타카하시군과 아오키군은 이 말을 사용하여 게임을 하려합니다.
2명은 처음 0점으로 시작합니다. 타카하시군부터 시작하여 교대로 조작합니다.

• 말은 한칸 오른쪽 혹은 한칸 아래로 이동합니다. 단, 말이 H행 W열의 칸을 벗어나는것은 불가능합니다. 말을 움직인 사람은 이동후의 칸이 파란 칸이라면 1점 득점하고, 빨간 칸이라면 1점 실점한다. 말을 움직일 수 없게 되면 게임을 종료합니다. 게임의 결과는 종료시의 2명의 점수가 다를 경우에는 점수가 큰 사람이 승리하며, 동일할 경우에는 무승부가 됩니다.
  타카하시군과 아오키군은 각각, 자신이 승리할수있는 최선의 행동을 한다고 했을때 게임의 결과를 구하시오.

【전제】

• 1 ≦ H, W ≦ 2000
• Aᵢⱼ은 + 혹은 -

【입력 형태】

H W
A₁₁A₁₂A₁₃ ... A₁w
A₂₁A₂₂A₂₃ ... A₂w
A₃₁A₃₂A₃₃ ... A₃w
...
Aₕ₁Aₕ₂Aₕ₃ ... Aₕw

타카하시군이 승리한다면 Takahashi라고, 아오키군이 승리한다면 Aoki라고, 무승부라면 Draw라고 출력하시오.

【예시】

입력 예 1

3 3
---
+-+
+--

출력 예 1

Takahashi

타카하시군은 다음과 같은 전략으로 이길 수 있습니다. 우선 타카하시군이 먼저 인형을 오른쪽으로 움직입니다. 이동한 칸은 빨간칸이므로 타카하시군은 1점을 잃고 타카하시군과 아오키군의 점수는 -1, 0이 됩니다.

• 이후 아오키군이 인형을 오른쪽으로 움직였다면 타카하시군은 인형을 아래로 움직입니다.
• 이후 아오키군이 인형을 아래로 움직였다면 타카하시군은 인형을 오른쪽으로 움직입니다. 어찌됬든 아오키군은 무조건 빨간칸으로 움직여야 합니다. 이렇게 되면 타카하시군은 1점을 얻고 아오키군은 1점을 잃으므로 0, -1이 됩니다. 그리고 현재 인형은 위에서 2번째, 왼쪽에서 3번째칸에 있기때문에 다음 이동에서 아오키군은 반드시 아래로 움직일 수 밖에 없고, 이동처가 붉은 칸이므로 최종 득점은 0, -2가 됩니다. 이후 인형을 움직일 수 없기때문에 게임은 종료되고 타카하시군의 승리입니다.

입력 예 2

2 4
+++-
-+-+

출력 예 2

Aoki

아오키군은 타카하시군이 어떻게 조작하더라도 잘 조작하면 승리할 수 있습니다.

입력 예 3

1 1
-

출력 예 3

Draw

이 게임은 즉시 종료되며 각 승자는 0점이기때문에 결과는 무승부가 됩니다.

출처 : https://atcoder.jp/contests/abc201/tasks/abc201_d