8008 : 체스판과 퀸
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 7
•통과: 2
•만든사람: suakii
문제 설명
$8 \times 8$ 크기의 체스판이 주어집니다. 이 체스판의 몇몇 칸에는 장애물(
장애물을 피해 서로를 공격할 수 없도록 8개의 퀸을 배치하는 방법의 수를 구하는 프로그램을 작성하십시오. 즉, 어떤 두 퀸도 같은 행, 열, 또는 대각선 상에 위치할 수 없습니다.
[제약 조건]
• 체스판의 크기는 항상 $8 \times 8$입니다.
• 각 칸은 빈 칸(
*)이 있어 퀸을 놓을 수 없습니다.장애물을 피해 서로를 공격할 수 없도록 8개의 퀸을 배치하는 방법의 수를 구하는 프로그램을 작성하십시오. 즉, 어떤 두 퀸도 같은 행, 열, 또는 대각선 상에 위치할 수 없습니다.
[제약 조건]
• 체스판의 크기는 항상 $8 \times 8$입니다.
• 각 칸은 빈 칸(
.) 또는 장애물(*)로 주어집니다.입력 설명
8줄에 걸쳐 체스판의 상태가 주어집니다. 각 줄은 8개의 문자로 이루어져 있습니다.
출력 설명
장애물을 피해 8개의 퀸을 안전하게 배치할 수 있는 유효한 경우의 수를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
........
........
..*.....
........
........
........
........
........
출력 예시
COPY
복사되었습니다!
복사되었습니다!
65도움
1행부터 8행까지 각 행마다 퀸을 하나씩 배치하는 백트래킹(N-Queens) 알고리즘을 사용합니다.
열, 좌하향 대각선($r+c$), 우하향 대각선($r-c+7$)의 사용 여부를 비트마스크나 불리언 배열로 관리하며, 장애물 칸(
열, 좌하향 대각선($r+c$), 우하향 대각선($r-c+7$)의 사용 여부를 비트마스크나 불리언 배열로 관리하며, 장애물 칸(
*)을 제외하고 탐색을 진행합니다.