측면 피해

바다에서 큰 배들로 배틀십 게임을 하고 있다. 정확히 말하면, 한 변의 길이가 최대 $100\times 100$인 정사각형 격자가 있고, 그 안에 배틀십에서 가장 큰 종류인 항공모함이 최대 $10$척 놓여 있다. 항공모함의 길이는 5칸이며, 가로 또는 세로로 놓인다. 배끼리는 겹치지 않지만 서로 인접해도 된다. 예시는 그림 L.1을 참고한다.

그림 L.1: 처음 네 번 발사한 뒤의 격자.

상대는 규칙을 제멋대로 구부리는 것 같다. 발사를 시작하기 전에 배의 위치를 항상 정해 두지는 않는다. 이 속임수가 마음에 들지 않으니, 그래도 게임에서 이기기로 한다.

목표는 상대의 항공모함을 모두 찾아서 침몰시키는 것이다. 최대 2500번 안에 모든 배의 칸 다섯 개를 각각 전부 맞혀야 한다.