題目描述

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?

輸入

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

輸出

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

樣例輸入?

........
........
..*.....
........
........
.....**.
...*....
........

樣例輸出

65

思路分析

1.任意兩皇后不能放在同一行、同一列、同一對角線上

2.采用回溯算法解決帶障礙物的八皇后問題，通過遞歸和條件判斷找出所有可行的放置方案并統計數量。

代碼

#include<bits/stdc++.h>
#define ll long long
using namespace std;
char chessboard[8][8];
ll ans,col[8];
int issafe(int i,int j){if(i==0)return 1;else{for(int k=0;k<i;k++){int a=abs(i-k),b=abs(j-col[k]);if(a==b||b==0)return 0;}return 1;}
}
void solve(int i){for(int j=0;j<8;j++){if(chessboard[i][j]!='*'){if(issafe(i,j)){if(i==7)ans++;else{col[i]=j;solve(i+1);}}}}
}
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);for(int i=0;i<8;i++){for(int j=0;j<8;j++){cin>>chessboard[i][j];}}solve(0);cout<<ans;return 0;
}