ZOJ Problem Set - 1002

Fire Net Time Limit: 2 Seconds Memory Limit: 65536 KB Suppose that we have a square city with straight streets. A map of a city is a square board with n rows and n columns, each representing a street or a piece of wall.

A blockhouse is a small castle that has four openings through which to shoot. The four openings are facing North, East, South, and West, respectively. There will be one machine gun shooting through each opening.

Here we assume that a bullet is so powerful that it can run across any distance and destroy a blockhouse on its way. On the other hand, a wall is so strongly built that can stop the bullets.

The goal is to place as many blockhouses in a city as possible so that no two can destroy each other. A configuration of blockhouses is legal provided that no two blockhouses are on the same horizontal row or vertical column in a map unless there is at least one wall separating them. In this problem we will consider small square cities (at most 4x4) that contain walls through which bullets cannot run through.

The following image shows five pictures of the same board. The first picture is the empty board, the second and third pictures show legal configurations, and the fourth and fifth pictures show illegal configurations. For this board, the maximum number of blockhouses in a legal configuration is 5; the second picture shows one way to do it, but there are several other ways.

Your task is to write a program that, given a description of a map, calculates the maximum number of blockhouses that can be placed in the city in a legal configuration.

The input file contains one or more map descriptions, followed by a line containing the number 0 that signals the end of the file. Each map description begins with a line containing a positive integer n that is the size of the city; n will be at most 4. The next n lines each describe one row of the map, with a ‘.’ indicating an open space and an uppercase ‘X’ indicating a wall. There are no spaces in the input file.

For each test case, output one line containing the maximum number of blockhouses that can be placed in the city in a legal configuration. 题意大致为： 在一个最大为4*4的方格内设置碉堡 条件 :

1. 两个及以上碉堡不能位于同一行或者同一列
2. 如果有墙，两个碉堡可以位于其两侧
3. 碉堡只能建在空地 输入0时，结束

摘自维基百科：深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

在4*4的区域内顺序编号进行遍历放置，find函数用四个循环从点（X,Y）上下左右判断，如果有碉堡返回0，如果有墙继续下个循环。然后再进行DFS。 traverse数组里，0没有东西，1放碉堡，2放防火墙。Count为放置个数，maxCount记录count的最大值，即题目要求值

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <memory.h>

using namespace std;

int traverse[10][10],maxCount,n,Count;

int find(int x,int y) // 判断是否可以放置
{
	for(int i=y; i>=1; i--) 
	{
		if( traverse[x][i] == 1 )
			return 0;
		if( traverse[x][i] == 2 )
			break;
	}
	for(int i=y; i<=n; i++)
	{
		if( traverse[x][i] == 1 )
			return 0;
		if( traverse[x][i] == 2 )
			break;
	}
	for(int i=x; i>=1; i--)
	{
		if( traverse[i][y] == 1 )
			return 0;
		if( traverse[i][y] == 2 )
			break;
	}
	for(int i=x; i<=n; i++)
	{
		if( traverse[i][y] == 1 )
			return 0;
		if( traverse[i][y] == 2 )
			break;
	}
	return 1;
}
//深度优先搜索
void DFS()
{
	if( Count > maxCount )
		maxCount = Count;
	for(int k=1; k<=n; k++)
		for(int h=1; h<=n; h++)
			if( !traverse[k][h] && find(k,h) )
			{
				traverse[k][h] = 1;
				Count++;
				DFS();
				traverse[k][h] = 0;
				Count--;
			}
}

int main()
{
	char str[10];
	while( cin >> n && n)
	{
		maxCount = 0; Count = 0;
		for(int i=1; i<=n; i++)
		{
			cin >> str;
			for(int k=0; k<n; k++)
			traverse[i][k+1] = (str[k] == 'X' ? 2 : 0 );
		}
		DFS();
		cout << maxCount << endl;
	}
    return 0;
}