Fire Net

思路

• 这里矩阵最多也只有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";
    }
}