Battlecheap
면접 대비시간 제한3초메모리 제한512 MB
10 곱하기 10 격자에 길이 3인 배를 놓는 모든 위치 중, 주어진 서로 다른 사격 좌표열에 배의 세 칸이 모두 맞지 않는 경우의 수를 센다.
문제
아주 긴 비행 중이라 너무 심심하다. 기내 엔터테인먼트 시스템에 들어 있는 형편없는 비디오 게임 목록을 넘기다가 흥미로운 것을 발견한다. 바로 Battleship이다! 10 곱하기 10 격자에서 두 사람이 하는 게임이고, 함대를 배치해 자기 배가 격침되기 전에 적 함선을 격침하는 것이 목표이다.
그러면 비행기를 타고 가면서 Battleship을 해 보면 재미있지 않을까? 아쉽게도 곧 그리 재미있지 않다는 것을 알게 된다. 기내 비디오 게임은 예산이 적고 버그가 많은 복제판이라 몇 가지 결정적인 결함이 있다.
- 길이 3칸, 너비 1칸인 순양함을 먼저 배치하는데, 그다음 배로 넘어가는 버튼이 리모컨에 없다. 그래서 잠시 후 게임이 자동으로 시작되고 그 배 하나만 배치된 상태가 된다.
- 컴퓨터는 자기 차례에 내 배를 향해 발사할 수 있지만, 내 차례가 되면 컴퓨터를 향해 발사하는 버튼도 리모컨에 매핑되어 있지 않다. 그래서 잠시 후 차례를 잃고 컴퓨터가 다시 나를 향해 발사한다.
- 다행히도 컴퓨터가 플레이하는 횟수에는 제한이 있는 것 같다. 일정 횟수만큼 발사한 뒤에도 내가 아직 지지 않았다면(즉 순양함의 모든 칸이 맞지 않았다면), 컴퓨터는 그냥 포기하고 내가 승자라고 선언한다.
- 게임의 난수 생성기도 완전히 고장 나 있다. 게임이 바뀌어도 무슨 일이 일어나든, 무엇을 맞히든, 순양함을 어디에 배치하든 컴퓨터는 항상 똑같은 순서로 칸을 발사한다.
물론 컴퓨터의 하드코딩된 수순을 파악하고 나면 이 게임은 완전히 실망스러워진다. 그래도 비행기 안에 갇혀 있으니, 이 수순을 알고 있을 때 이길 방법이 몇 가지인지, 즉 순양함을 배치하고 컴퓨터가 포기할 때까지 살아남는 방법이 몇 가지인지 궁금해진다.
입력
입력 파일은 여러 테스트 케이스로 이루어진다. 입력 파일의 첫 줄에는 테스트 케이스의 수를 나타내는 정수 하나가 있다. 각 테스트 케이스가 이어진다. 첫 줄에는 컴퓨터가 포기하기 전까지 발사하는 횟수를 나타내는 정수 이 하나 있다. 다음 개 줄은 컴퓨터가 발사하는 칸을 차례로 설명한다. 번째 줄에는 컴퓨터의 번째 발사가 향하는 행과 열을 나타내는 두 정수 , 이 있다. 컴퓨터는 자기 수순에서 같은 위치에 두 번 발사하지 않는다.
출력
입력의 각 테스트 케이스마다, 게임 시작 시 순양함을 배치하고 끝까지 살아남는 방법이 몇 가지인지 나타내는 정수 하나를 한 줄에 출력한다. 순양함은 세로로 인접하거나 가로로 인접한 3칸에 배치해야 하며, 컴퓨터의 수순이 순양함이 놓인 모든 칸을 맞히지 않으면 살아남는다.
힌트
이미지 저작권
