NYOJ 587-blockhouses | ZOJ 1002-Fire Net

题目来源

NYOJ 587-blockhouses http://acm.nyist.net/JudgeOnline/problem.php?pid=587
ZOJ 1002-Fire Net http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1002

时间限制:1000 ms | 内存限制:65535 KB | 难度:3

描述

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.
假设我们有一个正方形的城市街道。城市由一个n*n的方块组成,每一个方块代表一个街道或一块墙。

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.
目标是使得城市中尽可能多的碉堡没有办法两两摧毁对方。配置碉堡的规定是:不能有两个碉堡在同一水平或垂直线上,除非至少有一堵墙隔开。在这个问题上我们只考虑小城市广场,最多4x4且含有子弹无法穿过的墙壁。

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.
下图显示了同一个方块的五张图片。第一张图片是空的,第二和第三张图片是合法配置,而第四和第五张图片为非法配置。在这一大方块中,合法配置的碉堡的最大数目为5。第二张图片展示了一种方式,但也有一些其他的方法。

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.
输入文件包含一个或多个地图描述,最后一行的数字0表示输入结束。每个地图的第一行是一个正整数n,表示城市的规模;n最大为4。接下来的n行每行描述一个排的地图,“.”表示一个开放的空间,一个大写的“X”表示墙。输入文件中没有空格。

输出

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
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0

样例输出

5
1
5
2
4

自己翻译,水平有限……

算法思路

  • 典型的广搜思路,与八皇后非常类似,DFS试一下,ac了……

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
using namespace std;
int i,j,n,op;
int m[4][4];//正方形城市最大为4*4

int check(int r, int c){//检查:上面以及左边有无碉堡
for(i=r; i>=0; i--){//靠近自己开始搜,因为有可能有墙阻隔
if(m[i][c]==2 || m[i][c]==1){
if(m[i][c]==2) return 0;
break;
}
}
for(i=c; i>=0; i--){
if(m[r][i]==2 || m[r][i]==1){
if(m[r][i]==2) return 0;
break;
}
}
return 1;
}

void dfs(int now, int sum){
int r = now/n, c = now%n;
if(now==n*n){
if(sum>op) op = sum;
return;
}
if(m[r][c]==0){
if(check(r,c)){
m[r][c] = 2;//标记
dfs(now+1,sum+1);
m[r][c] = 0;//反标记,广搜
}
}
dfs(now+1,sum);
}

int main(){
char x;
cin>>n;
while(n){
for(i=0; i<n; i++)
for(j=0; j<n; j++){//转不转化为int数组其实无所谓……
cin>>x;
if(x==46) m[i][j]=0;
else m[i][j]=1;
}
op = 0;
dfs(0,0);
cout<<op<<endl;
cin>>n;
}
return 0;
}
文章目录
  1. 1. 算法思路
  2. 2. 算法实现

20160418-acm-11/

本页二维码