초콜릿 쪼개기 게임
시간 제한1초메모리 제한1024 MB
N×M 초콜릿에서 두 사람이 번갈아 조각 하나의 가장자리가 아닌 행이나 열을 떼어 먹는다. 움직일 수 없는 사람이 지며, 최적으로 두었을 때 누가 이기는지 구한다.
문제
서현과 현서는 격자 모양의 초콜릿을 쪼개 먹으려고 한다. 하지만 커다란 초콜릿을 쪼개는 일은 너무 지루해서 둘은 게임을 하기로 했다. 게임은 서현부터 시작하여 번갈아 턴을 진행한다. 자신의 턴이 되면 초콜릿 조각 중 하나를 고르고, 그 조각에서 가로줄 또는 세로줄 하나를 고른다. 단, 맨 위나 아래 가로줄, 또는 맨 왼쪽이나 오른쪽 세로줄은 고를 수 없다. 그다음 고른 줄을 먹고 조각을 나머지 두 조각으로 쪼갠다. 자신의 턴에 행동할 수 없는 플레이어가 진다. 초콜릿이 너무 커서 둘은 게임을 하는 것에도 지쳐버렸다. 둘 모두 최선의 전략을 쓴다면 누가 이기는지 구하라.
입력
초콜릿의 세로 길이 과 가로 길이 이 공백으로 구분되어 차례로 주어진다.
출력
서현이 이기면 sh를, 현서가 이기면 hs를 출력한다.
제한
힌트
조각은 쪼갤 수 없다. 조각은 가운데 줄을 먹어 조각 두 개로 쪼개는 경우밖에 없다.