思路
- 这里矩阵最多也只有4*4,所以直接暴力dfs即可,具体看代码
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
char f[10][10];
int ans;
int now[10][10];
int n;
bool solve(int x,int y){
bool flag=true;
for(int i=x-1;i>=0&&flag;i--){
if(f[i][y]=='X')break;
if(now[i][y])flag=false;
}
for(int i=x+1;i<n&&flag;i++){
if(f[i][y]=='X')break;
if(now[i][y])flag=false;
}
for(int i=y-1;i>=0&&flag;i--){
if(f[x][i]=='X')break;
if(now[x][i])flag=false;
}
for(int i=y+1;i<n&&flag;i++){
if(f[i][y]=='X')break;
if(now[i][y])flag=false;
}
return flag;
}
void dfs(int k,int num){
int x=k/n;
int y=k%n;
if(k>=n*n){
ans=max(num,ans);
return;
}
if(f[x][y]!='X'&&solve(x,y)){
now[x][y]=1;
dfs(k+1,num+1);
now[x][y]=0;
}
dfs(k+1,num);
}
int main(){
while(cin >> n,n){
memset(now,0,sizeof now);
ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
cin >> f[i][j];
}
}
dfs(0,0);
cout << ans << "\n";
}
}