/* Name: NYOJ--587--blockhouses Author: shen_渊 Date: 16/04/17 21:43 Description: dfs,逐个点深度优先搜索,不管能不能放炮台都得继续搜索,能放时考虑放不放 */#include#include 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 >map[i]; dfs(0,0); cout< < 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;}