杰拉斯的博客

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 

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 

that is the size of the city; 

will be at most 4. The next 

lines each describe one row of the map, with a '

' indicating an open space and an uppercase '

' 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.

(阅读全文…)

从实验三开始使用scanf与printf进入输入输出，具体原因详见：[ACM学习心得]关于sync_with_stdio(false);

实验项目：ACM程序设计基础(1)
实验目的：掌握C++程序设计基础。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1．输入年、月、日，计算该日是该年的第n天，输出n。

2．对于大于等于6的偶数，可以表示为2个素数之和，请判断一个数是否是对称数，如果该数为对称数而且是偶数，输出其和等于该数的2个素数。

3．Fire Net问题， 要求输出最优值和最优值对应的最优解。

4．附加题：0-1背包问题：有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。物品（1.可以;2.不可）切割出来只是装一部分，求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大，先输入物品数n和背包容量v，然后输入各个物品费用和价值，输出最大价值。

(阅读全文…)

实验项目：C++STL泛型编程（2）
实验目的：掌握C++STL string向量容器等的应用。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1.输入一串小写字母字符，输出该字符串中每个字母的个数，例如输入：aadsef，输出：
a 2
d 1
e 1
f 1
s 1

2. 古代一位国王和他的张、王、李、赵、钱五位将军一同出外打猎，各人的箭上都刻有自己的姓氏。打猎中，一只鹿中箭倒下，但不知是何人所射。
张说："或者是我射中的，或者是李将军射中的。"
王说："不是钱将军射中的。"
李说："如果不是赵将军射中的，那么一定是王将军射中的。"
赵说："既不是我射中的，也不是王将军射中的。"
钱说："既不是李将军射中的，也不是张将军射中的。"
国王让人把射中鹿的箭拿来，看了看，说："你们五位将军的猜测，只有两个人的话是真的."请判断是谁射中鹿。

3. 输入一个自然数Ｎ（2≤N≤9），要求输出如下的魔方阵，即边长为N行N列，元素取值为1至N*N，1在左上角，呈顺时针方向依次放置各元素。如输入4，输出：
1 2 3 412  13  14   511  16  15   610   9   8   7

附加题：
给定一个N×M的整数矩阵，找出其中具有最大和的子矩阵。一个矩阵的和就是矩阵中所有元素的和，子矩阵是指位于整个矩阵中任何一个1×1或更大的连续的子矩阵。

(阅读全文…)

实验项目：C++STL泛型编程（1）
实验目的：掌握C++STL vector向量容器、stack堆容器和queue队列容器的应用。
实验要求：使用VC++6.0实现实验要求。
实验内容：

1.利用vector向量容器，实现1—n个数围成一圈，隔3输出，输出最后的顺序号。
2.利用stack堆栈容器，实现输入一个算术表达式中包含圆括弧、方括弧和花括弧三种类型的括弧，输出是否正确配对。例如：
输入：{4\[6*(8+9)]}+6}
输出：不匹配
3.利用queue队列容器实现杨辉三角，根据输入的n，输出对应的杨辉三角（猛击进入相应OJ题目）。
4.附加题：
一矩形阵列由0到9组成，数字1到9代表细胞，细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞，求给定矩阵整列的细胞个数

(阅读全文…)

版本号(version number)是版本的标识号。每一个操作系统（或广义的讲，每一个软件）都有一个版本号。版本号能使用户了解所使用的操作系统是否为最新的版本以及它所提供的功能与设施。

当前软件的版本号命名方式众多，之前windows版本有95、98、2000、2003,后有XP、vista，随后沿用开发代号: Windows 7。windows的版本命名一度影响了国内众多软件，像QQ、金山、瑞星等等。

版本命名风格主要有GNU 风格和windows风格，每一个版本号可以分为主版本号与次版本号两部分。例如：DOS4.0，主版本号是4，次版本号是0。

一、 GNU 风格的版本号命名格式
主版本号 . 子版本号 [. 修正版本号 [. 编译版本号 ]]
英文对照 : Major_Version_Number.Minor_Version_Number[.Revision_Number[.Build_Number]]
示例 : 1.2.1, 2.0, 5.0.0 build-13124

二、 Windows 风格的版本号命名格式
主版本号 . 子版本号 [ 修正版本号 [. 编译版本号 ]]
英文对照 : Major_Version_Number.Minor_Version_Number[Revision_Number[.Build_Number]]
示例: 1.21, 2.0

应根据下面的约定使用这些部分：
Major ：具有相同名称但不同主版本号的程序集不可互换。例如，这适用于对产品的大量重写，这些重写使得无法实现向后兼容性。
Minor ：如果两个程序集的名称和主版本号相同，而次版本号不同，这指示显著增强，但照顾到了向后兼容性。例如，这适用于产品的修正版或完全向后兼容的新版本。
Build ：内部版本号的不同表示对相同源所作的重新编译。这适合于更改处理器、平台或编译器的情况。
Revision ：名称、主版本号和次版本号都相同但修订号不同的程序集应是完全可互换的。这适用于修复以前发布的程序集中的安全漏洞。

下面再例举一些常见的版本命名：
Alpha -- 内部测试版
Beta -- 外部测试版
CHT -- 繁体中文版
CN/SPC -- 简体中文版
EN -- 英文版
Demo -- 演示版
Dev -- 开发专用版，程序员版本。
Free -- 免费版
Professional -- 专业版
Enterprise--企业版
Ultimate -- 旗舰版，最终版本
Upgrade -- 升级版
OEM版 --OEM 版通常是捆绑在硬件中而不单独销售的版本。将自己的产品交给别的公司去卖，保留自己的著作权，双方互惠互利，一举两得。