ZOJ 1002 Fire Net 分析与解答

Problem:

Fire Net

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.

Sample input:

4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0

Sample output:

5 1 5 2 4

Analysis:

地图的每个位置有以下几种状态:

空闲(NO),墙(WALL),城堡(BLOCK),处于其他城堡射程.

遍历每一行，在每一行的两墙之间，寻找这样的位置，此位置若建设城堡，可及的视野最小。找到后，建设城堡，并标记其视野为“OCCPY（占用）“。在此行的下一个墙间间隔进行同样的操作，若没有这样的间隔，转向下一行，进行同样的操作。

Attention:

注意输入输出的格式要严格按照要求,否则submit后不会AC的.望上到处有这方面的帖子,OJ上也有教程.本人第一次提交,算法是正确的,因为输入输出格式提交了两次错误的代码.一定要认真审题.

上次的代码有逻辑错误，但在ZOJ和杭电OJ上都AC了。后来被我找到一个逻辑错误如下，若在以下情况：

. . . .

. . . .

XXX .

XXX .

正确答案是3，在（1，1）（2，2），（3，4）建设城堡。

但错误程序的结果是2，因为按错误的逻辑，第一次便将城堡建设在（1，4）位置，第二个在（2，3），然后就没有然后了。

传说ZOJ上数据比较刁钻，但还是被我不小心钻了空子啦，这道题上其测试数据有点小问题啊^_^。修改后的程序也AC了，自己也找了许多数据测试过，是正确的，逻辑上也是正确的。代码比较长～

附上上次有错误的代码，以供参考：

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 	50
#define NO 		0
#define WALL 		-1
#define BLOCK		-2
#define BOOL 		int
#define TRUE		1
#define FALSE		0
int city[MAX_SIZE][MAX_SIZE];
int count = 0;
int size;
void add_block(int i, int j)
{
	BOOL flag = FALSE;
		int t, left;
		for(t = 0; t < j; ++t)
			if(city[i][t] == WALL)
			{
				flag = TRUE;
				left = t + 1;
			}
		if(!flag)
			left = 0;
		for (t = left; t < size; t += 1)
		{
			if(city[i][t] == WALL)
				break;
			if(city[i][t] == NO && t != j)
				++city[i][t];
		}
		flag = FALSE;
		for(t = 0; t < i; ++t)
			if(city[t][j] == WALL)
			{
				flag = TRUE;
				left = t + 1;
			}
		if(!flag)
			left = 0;
		for (t = left; t < size; t += 1)
		{
			if(city[t][j] == WALL)
				break;
			if(city[t][j] == NO && t != i)
				++city[t][j];
		}
		city[i][j] = BLOCK;
		++count; 
}
int detect(int i, int j)
{
	int a;
	BOOL ret = FALSE;
	for (a = j + 1; a < size; a += 1)
	{
		if(city[i][a] == NO)
			ret = TRUE;
		if(city[i][a] == WALL)
			break;
	}
	if(ret == FALSE)
		return TRUE;
	if(((((j+1)<size)?(city[i][j+1] == NO ):FALSE) || (((j-1)>=0)?(city[i][j-1] == NO ):FALSE)) && ((((i-1)>=0)?(city[i-1][j] == NO):FALSE) || (((i+1)<size)?(city[i+1][j] == NO):FALSE)))
		return FALSE;
	else 
		return TRUE;
}
int main(void)
{
	int i, j;
	char c;
	while(scanf("%d",&size) != EOF)
	{
		count = 0;
		if( size == 0)
			break;
		for (i = 0; i < size; i += 1)
		{
			j = 0;
			while(j < size)
			{
				scanf("%c",&c);
				if(c == '.')
					city[i][j] = NO;
				else if(c == 'X')
					city[i][j] = WALL;
				else if(c == '/n')
					continue;
				else
				{
					printf("Invalid Input!/n");
					exit(-1);
				}
				++j;
			}
		}
		for(i = 0; i < size; ++i)
			for(j = 0; j < size; ++j)
			{	if(city[i][j] == NO)
				{
					if(detect(i,j))
						add_block(i,j);
				}
			}
		printf("%d/n",count);
	}
	return 0;
}

Solution(C语言):

#include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 	50
#define NO 		0
#define WALL 		-1
#define BLOCK		-2
#define OCCUPY		1
#define BOOL 		int
#define TRUE		1
#define FALSE		0
int city[MAX_SIZE][MAX_SIZE];
int count = 0;
int size;
int add_block(int i, int j)//在当前行中的两墙间寻找最佳位置添加城堡，返回此间隔的下一个位置
{
	BOOL flag = FALSE;
	int t, v, left, ret, vision, min_c, min_v;
	min_c = -1;
	min_v = size + 1;
	for(t = j; t < size; ++t)		//遍历当前行中的两墙间所有位置，找到可及视野最小的一个位置
	{
		if(city[i][t] == WALL)
			break;
		if(city[i][t] != NO)//跳过占用的位置
			continue;
		vision = 0;
		for(v = i; v < size; ++v)
		{
			if(city[v][t] == NO)
				++vision;
			else
				break;
		}
		if(vision < min_v)
		{
			min_v = vision;
			min_c = t;
		}
	}
	if(min_c == -1)
		return size;
	//将选择的位置所在列所有空位标记为“占用”
	flag = FALSE;
	for(t = 0; t < i; ++t)
		if(city[t][min_c] == WALL)
		{
			flag = TRUE;
			left = t + 1;
		}
	if(!flag)
		left = 0;
	for (t = left; t < size; t += 1)
	{
		if(city[t][min_c] == WALL)
			break;
		if(t != i)
			city[t][min_c] = OCCUPY;
	}
	for(t = j; t < size; ++t)//将当前行的当前位置的两墙之间标记为“占用”
	{
		if(city[i][t] == WALL)
		{
			ret = t;
			break;
		}
		city[i][t] = OCCUPY;
	}
	if(t == size)
		ret = size;
	city[i][min_c] = BLOCK;		//建设城堡
	++count;
	return ret; 
}
int main(void)
{
	int i, j, next;
	char c;
	while(scanf("%d",&size) != EOF)//注意OJ上输入输出的格式和方式
	{
		count = 0;
		if( size == 0)
			break;
		for (i = 0; i < size; i += 1)
		{
			j = 0;
			while(j < size)
			{
				scanf("%c",&c);
				if(c == '.')
					city[i][j] = NO;
				else if(c == 'X')
					city[i][j] = WALL;
				else if(c == '/n')
					continue;
				else
				{
					printf("Invalid Input!/n");
					exit(-1);
				}
				++j;
			}
		}
		for(i = 0; i < size; ++i)
		{
			next = 0;
			while(next < size)
			{
				while(next < size && city[i][next] != NO)//找到本行上一次添加城堡（若没有就找到第一个空位）之后的第一个空位
					++next;
				if(next < size)
					next = add_block(i,next);
			}	
		}
		printf("%d/n",count);
	}
	return 0;
}