미니 배틀쉽
시간 제한6초메모리 제한512 MB
n×n 격자에 주어진 크기의 서로 다른 k척의 배를 배치해 명중, 빗나감, 빈칸 정보와 모두 일치하는 경우의 수를 센다.
문제
배틀쉽은 두 사람이 하는 게임이다. 각 플레이어는 상대방에게 보이지 않는 자신만의 격자를 가지고 있다. 각 플레이어는 자신의 격자에 여러 척의 배를 몰래 배치한다. 각 배는 하나 이상의 연속한 칸으로 이루어진 가로 또는 세로 직선을 차지한다. 배끼리 겹칠 수 없다. 크기가 같더라도 모든 배는 서로 다른 것으로 취급한다.
배를 배치한 뒤, 플레이어들은 번갈아 가며 상대방 격자의 좌표를 불러 상대방의 배에 사격한다. 상대방은 그 사격이 명중인지 빗나갔는지 정직하게 말해야 한다. 어떤 배의 모든 칸이 명중하면 그 배는 침몰한다(“You sunk my battleship!!”). 자신의 배가 모두 침몰한 플레이어가 패배한다.
Bob은 Alice와 미니 배틀쉽을 하고 있다. 일반 배틀쉽은 10×10 격자에서 배 5척으로 진행한다. 미니 배틀쉽은 훨씬 작아서 격자가 5×5보다 클 수 없고 배도 5척보다 적을 수 있다.
Bob은 지금까지 알아낸 정보를 바탕으로 Alice의 보드에 배를 배치할 수 있는 경우의 수가 몇 가지인지 궁금해한다. Alice가 속임수를 쓰고 있다면, 또는 게임 상황 자체가 불가능하다면 답은 0이다.
입력
첫째 줄에 공백으로 구분된 두 정수 n (1 ≤ n ≤ 5)과 k (1 ≤ k ≤ 5)가 주어진다. 이는 n×n 격자에서 배 k척으로 진행하는 미니 배틀쉽 게임을 나타낸다.
다음 n개 줄에는 각각 문자열 s (|s| = n)가 주어진다. 이는 Bob이 지금까지 본 Alice의 격자이다.
- 문자 ‘X’는 Bob의 사격이 빗나간 칸이다.
- 문자 ‘O’(숫자 0이 아니라 알파벳 O)는 Bob의 사격이 명중한 칸이다.
- 점(‘.’)은 Bob이 아직 사격하지 않은 칸이다.
다음 k개 줄에는 각각 정수 x (1 ≤ x ≤ n)가 하나씩 주어진다. 이는 배들의 크기이다.
출력
Bob이 본 것과 일치하도록 k척의 서로 다른 배를 Alice의 격자에 배치할 수 있는 경우의 수를 정수 하나로 출력한다.