hdu--1045--Fire Net,NYOJ--587--dfs--blockhouses

/*
    Name: NYOJ--587--blockhouses
    Author: shen_渊 
    Date: 16/04/17 21:43
    Description: dfs,逐个点深度优先搜索，不管能不能放炮台都得继续搜索，能放时考虑放不放 
*/
#include<cstring>
#include<iostream>
using namespace std;
bool check(int,int);
void dfs(int,int);
char map[5][5];
int n,max_battle;
int main()
{
//    freopen("in.txt","r",stdin);
    ios::sync_with_stdio(false);
    while(cin>>n,n){
        memset(map,0,sizeof(map));
        max_battle = 0;
        for(int i=0; i<n; ++i)cin>>map[i];
        dfs(0,0);
        cout<<max_battle<<endl;
    }
    return 0;
}
void dfs(int p,int ct){
    int x = p/n;
    int y = p%n;
    if(p==n*n){
        if(ct > max_battle)max_battle = ct;
        return ;
    }
    if(map[x][y] == '.' && check(x,y))
    {
        map[x][y] = 'b';
        dfs(p+1,ct+1);
        map[x][y] = '.';
//        dfs(p+1,ct);错了 如果不能放炮台，还得继续走的 
    }
    dfs(p+1,ct);
}
bool check(int x,int y){
    int flag = 1;
    for(int i=x; i>=0; i--){
        if(map[i][y] == 'X')break;
        if(map[i][y] == 'b'){
            flag = 0;break;
        }
    }
    for(int j=y; j>=0; j--){
        if(map[x][j] == 'X')break;
        if(map[x][j] == 'b'){
            flag = 0;break;
        }
    }
    return flag;
}