마법진 배치
실버 V의견: 0
마법사 리세는 \(N \times N\) 격자 위에 마법 수정을 정확히 \(K\)개 놓으려 한다. 수정은 같은 행이나 열에 두 개 이상 놓이면 서로 간섭하여 폭발하므로, 배치된 수정끼리는 행도 열도 달라야 한다.
격자의 일부 칸은 마법으로 봉인되어 수정을 놓을 수 없다. 봉인된 칸이 \(B\)개 주어질 때, 조건을 만족하는 배치의 수를 구하여라.
- \(1 \le K \le N \le 8\)
- \(0 \le B \le 10\)
- 봉인된 칸은 서로 다르며, 격자 안에 있다.
첫째 줄에 격자의 크기 \(N\), 수정의 수 \(K\), 봉인된 칸의 수 \(B\)가 공백으로 구분되어 주어진다.
다음 \(B\)개의 줄에 봉인된 칸의 행 번호와 열 번호가 공백으로 구분되어 주어진다. 행과 열 번호는 \(1\)부터 시작한다.
조건을 만족하는 배치의 수를 출력한다.
4 2 0
72
\(4 \times 4\) 격자에서 같은 행·열에 없도록 수정을 \(2\)개 놓는 방법은 \(72\)가지이다.
4 2 2
1 1
2 2
55
\((1,1)\)과 \((2,2)\)가 막혀 있어 일부 배치가 불가능하다. 남은 배치 수를 구한다.
막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
마법진 배치
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
마법진 배치