ZOJ 1002 Fire Net

题目大意：有一个4*4的城市，其中一些格子有墙（X表示墙），在剩余的区域放置碉堡。子弹不能穿透墙壁。问最多可以放置几个碉堡，保证它们不会相互误伤。

解法：从左上的顶点开始遍历，如果这个点不是墙，做深度优先搜索，算出这种情况下的最多碉堡数。每做一次DFS，更新一次最大值。

参考代码：

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;

char city[6][6];
int i,j,n,ans,maxi,visited[6][6];
void DSF();
int find(int x,int y);

int main(){
	while(cin>>n&&n){
		memset(city,‘X‘,sizeof(city));		//this is included in <string.h>
		memset(visited,0,sizeof(visited));
		ans=maxi=0;
		getchar();		//this is included in <cstdio.h>
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++)
				cin>>city[i][j];
			getchar();
		}
		DSF();
		cout<<ans<<endl;
	}


	return 0;
}

void DSF(){
	int r,c;
	if(ans<maxi) ans=maxi;
	for(r=1;r<=n;r++){			//intially it is a loop to sweep all the blocks in the city
		for(c=1;c<=n;c++){
			if(!visited[r][c]&&city[r][c]!=‘X‘){
				if(find(r,c)){		// check if can put a castle in this block 
					visited[r][c]=1;	//put a castle and the number of castle increase by one
					maxi++;			
					DSF();		//continue search, similar to pushing this block into stack
					visited[r][c]=0;	//return and number of castle minus one
					maxi--;
				}
			}
		}
	}
}
int find(int x,int y){
	int i;
	for(i=x-1;i>0;i++){		//check if there is castle in front, from the nearest to furthest
		if(visited[i][y]==1) return 0;	
		if(city[i][y]==‘X‘) break;	//if there has a wall, no problem, continue to next direction
	}
	for(i=y-1;i>0;i++){				//left
		if(visited[x][i]==1) return 0;
		if(city[x][i]==‘X‘) break;
	}
	for(i=x+1;i<=n;i++){			//back
		if(visited[i][y]==1) return 0;
		if(city[i][y]==‘X‘) break;
	}
	for(i=y+1;i<=n;i++){			//right
		if(visited[x][i]==1) return 0;
		if(city[x][i]==‘X‘) break;
	}
	return 1;		
}

ZOJ 1002 Fire Net,古老的榕树,5-wow.com