Chessboard and Queens

题目描述

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;
}