用dfs来做~~但注意每次dfs回来后需要恢复到进入dfs前的状态。。。
/**
map 0表示无wall houseblock
1表示 houseblock
-1表示wall
flagr 0 表示指定行无wall houseblock
1表示指定行有houseblock
-1表示指定行有wall 当指定行有wall时，优先级最高，一定为-1；
flagc 与flagr相近 对列的描述
根据flag* 标记情况来对一些情况进行筛选
**/
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int map[4][4],flagr[4],flagc[4],s,n,maxs;
void print()
{
int i,j;
cout<<"$$$$$$\n";
for(i=0;i<n;i++){
for(j=0;j<n;j++)
cout<<map[i][j]<<" ";
cout<<endl;
}
cout<<endl;
for(i=0;i<n;i++){
cout<<flagr[i]<<" ";
}
cout<<endl;
for(i=0;i<n;i++){
cout<<flagc[i]<<" ";
}
cout<<endl;
cout<<"@@@@@@\n\n";
}
//判断 x，y位置是否可以放置houseblock
int check(int x,int y){
int i,j;
//行中有墙的情况
if(flagr[x]==-1){
for(j=y-1;j>=0;j--){
if(map[x][j]){
if(map[x][j]==1)return 0;
break;
}
}
for(j=y+1;j<n;j++)
if(map[x][j]){
if(map[x][j]==1)return 0;
break;
}
}
//列中有墙的情况
if(flagc[y]==-1){
for(i=x-1;i>=0;i--){
if(map[i][y]){
if(map[i][y]==1)return 0;
break;
}
}
for(i=x+1;i<n;i++)
if(map[i][y]){
if(map[i][y]==1)return 0;
break;
}
}
return 1;
}
void dfs(){
int i,j,tempr,tempc;
for(i=0;i<n;i++){
if(flagr[i]!=1){
for(j=0;j<n;j++)
if(flagc[j]!=1&&!map[i][j]&&check(i,j)){
//修改状态
s++;
map[i][j]=1;
if(!flagr[i])flagr[i]=1;
if(!flagc[j])flagc[j]=1;
//print();
dfs();
//恢复状态
s--;
map[i][j]=0;
if(flagr[i]==1)flagr[i]=0;
if(flagc[j]==1)flagc[j]=0;
}
}
}
if(maxs<s)maxs=s;
}
int main()
{
int i,j,tempc,tempr;
char x;
while(cin>>n,n){
for(i=0;i<n;i++)flagr[i]=flagc[i]=0;
for(i=0;i<n;i++)
{
getchar();
for(j=0;j<n;j++)
{
cin>>x;
if(x==‘.‘){
map[i][j]=0;
}else{
map[i][j]=-1;
flagr[i]=-1;
flagc[j]=-1;
}
}
}
s=maxs=0;
dfs();
cout<<maxs<<endl;
}
return 0;
}