[C++] [CSES] Chessboard and Queens (Introductory Problems)

CSES의 열 일곱번째 문제입니다.

8*8체스판에서 8개의 퀸을 서로가 공격하지 못하게 놓는 경우의 수를 구하는 문제입니다.

이 문제에서는 퀸을 놓지 못하는 자리가 있습니다. 하지만 공격을 할 때에는 무시하는 자리입니다.

N-Queen 문제와 거의 비슷합니다.

 

Task

 

Your task is to place eight queens on a chessboard so that no two queens are attacking each other. As an additional challenge, each square is either free or reserved, and you can only place queens on the free squares. However, the reserved squares do not prevent queens from attacking each other.

How many possible ways are there to place the queens?

Input

The input has eight lines, and each of them has eight characters. Each square is either free (.) or reserved (*).

Output

Print one integer: the number of ways you can place the queens.

Example

Input:
........
........
..*.....
........
........
.....**.
...*....
........

Output:
65

 

Code

#include<bits/stdc++.h>
using namespace std;

vector<string> v(8);
int ans, r[10], c[10], dl[20], dr[20];
void chess(int row){
    if (row == 8){
        ans++;
        return;
    }
    for (int col=0;col<8;col++){
        if (v[row][col]=='*') continue;
        if (!r[row] && !c[col] && !dl[row+col] && !dr[8+row-col]){
            r[row] = 1, c[col] = 1, dl[row+col] = 1, dr[8+row-col] = 1;
            chess(row+1);
            r[row] = 0, c[col] = 0, dl[row+col] = 0, dr[8+row-col] = 0;
        }
    }
}
int main(){
    for (int i=0;i<8;i++) cin >> v[i];
    chess(0);
    cout << ans;
}

생각해야 하는 것

• 각 행 기준으로 어디 놓을 것인지를 체크해야 합니다.
• 저는 해당 열, 해당 행, 대각선 2개 배열까지 해서 총 4개의 visited 배열을 사용했습니다.
• 윗 상단, 윗 하단을 바라보는 대각선을 방문처리하는 데에 시간을 많이 썼습니다.
• 중고등학교 시절 그래프의 기울기가 +/-에 따라 모양이 바뀌는 것을 떠올려 식을 세울 수 있었습니다.
• '*'을 만나면 바로 다음 칸으로 가게 설정했습니다.