zoj 1002 Fire Net

用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;
}