Fire Net
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 2427 Accepted Submission(s): 1380
Problem Description
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.
Input
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.
Output
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
题目大意:给你一幅图,再给你一些点,这些点的上下左右不能再放其他点,除非有墙隔着,问最多可以放多少个这样的点。
首先这道题一看,明显用dfs就可以搞定,但是现在在看二分图专题,有这道题,然后查了一下,原来还真能用二分图,方法非常的巧妙啊!只要建了图就能够轻松解决,效率比dfs高很多!
重点是建图:要建两幅图,行一幅,列一幅,然后map[行][列]建立关系,这样就建完了。最后就是用二分图匈牙利算法秒杀!
链接:http://acm.hdu.edu.cn/showproblem.php?pid=1045
代码:
#include <iostream>
#include <stdio.h>
#include <memory.h>
using namespace std;
const int N = 15;
int a[N][N], b[N][N], pre[N];
char ch[N][N];
bool visit[N][N], map[N][N], flag[N];
int n, ans1, ans2;
void bulid()
{
int i, j, k;
memset(visit, false, sizeof(visit));
ans1 = 1;
for(i = 1; i <= n; i++) //行
{
for(j = 1; j <= n; j++)
{
if(!visit[i][j] && ch[i][j] != 'X')
{
k = j;
while(k <= n && ch[i][k] != 'X')
{
a[i][k] = ans1;
visit[i][k] = true;
k++;
}
ans1++;
}
}
}
memset(visit, false, sizeof(visit));
ans2 = 1;
for(i = 1; i <= n; i++) //列
{
for(j = 1; j <= n; j++)
{
if(!visit[i][j] && ch[i][j] != 'X')
{
k = i;
while(k <= n && ch[k][j] != 'X')
{
b[k][j] = ans2;
visit[k][j] = true;
k++;
}
ans2++;
}
}
}
for(i = 1; i <= n; i++)
{
for(j = 1; j <= n; j++)
{
map[ a[i][j] ][ b[i][j] ] = true;
}
}
}
int find(int cur)
{
int i;
for(i = 1; i < ans2; i++)
{
if(map[cur][i] && !flag[i])
{
flag[i] = true;
if(pre[i] == -1 || find(pre[i]))
{
pre[i] = cur;
return 1;
}
}
}
return 0;
}
int main()
{
int i, j, sum;
while(scanf("%d", &n), n)
{
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
cin >> ch[i][j];
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(map, 0, sizeof(map));
memset(pre, -1, sizeof(pre));
bulid();
sum = 0;
for(i = 1; i < ans1; i++)
{
memset(flag, 0, sizeof(flag));
sum += find(i);
}
printf("%d\n", sum);
}
return 0;
}
- 大小: 5.3 KB
分享到:
相关推荐
二分图的完美匹配是指在一个图中,每个顶点恰好被一条边连接,使得图中的所有顶点都被连接且没有多余未使用的边。在实际应用中,二分图的完美匹配常常出现在分配问题、调度问题等领域。KM算法,即Kuhn-Munkres算法,...
15. **FireNet (HDU 1045)** - **知识点**:行列匹配变形问题。 - **解题思路**:构建行列二分图模型,根据题目要求调整匹配条件,使用最大匹配算法求解。 16. **TaxiCab Scheme (HDU 1350)** - **知识点**:...
HDU(杭州电子科技大学在线评测系统)是一个深受程序员喜爱的在线编程练习平台,它提供了丰富的算法题目供用户挑战,帮助他们提升编程技能和算法理解能力。"hdu.rar_hdu"这个压缩包文件很可能是某位程序员整理的他在...
8. **图论与树**:HDU题目中可能涉及图的遍历(深度优先搜索DFS、广度优先搜索BFS)、树的遍历(前序、中序、后序)以及最小生成树、最短路径等算法。 9. **动态规划**:这是一种优化策略,通过构建状态转移方程来...
DFS是一种用于遍历或搜索树或图的算法。在这个过程中,算法从根节点开始探索尽可能深的子节点路径。当到达最深的叶子节点时,它会回溯到最近的一个未完成探索的节点,并继续进行探索。 **实现方法:** DFS通常有两...
题目HDU-3478 Catch涉及了二分图的检测,其中的关键在于理解题目的背景。题目描述了一个场景,即警察想知道小偷是否能够在某个时刻出现在任何位置。通过分析可知,如果图不是连通的或者不是二分图,则小偷不能同时...
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
2. 图的遍历:深度优先搜索(DFS)、广度优先搜索(BFS)等。 * 题目1043:Eight,涉及到多种解决方法。 * 题目1044:Collect More Jewels,涉及到动态规划(DP)的概念。 3. 图的搜索:图的搜索算法、图的路径查找...
这个课件可能介绍了二分图的定义、性质,以及最大匹配算法,如Kuhn-Munkres算法或匈牙利算法。 10. **课件10: 母函数及其应用_new** 母函数是解决序列和问题的有效工具,尤其在处理递推序列时。这个课件可能解释了...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
1. **深度优先搜索(DFS, Depth-First Search)**:DFS是一种遍历或搜索树(或图)的算法,它沿着树的深度方向进行探索,直到达到叶子节点或者回溯到一个未被访问的分支。DFS通常用于解决连通性问题,如判断图是否...
八数码的A*算法~不是很高效,但是很适合刚刚学这个算法的朋友们
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
二分图匹配实例代码及整理 1、匈牙利算法 HDU 1150 #include #include #include using namespace std; int m,n,k; int vis[105]; int mpt[105][105]; int use[105]; int hungary(int x) { for(int i=1;i<m;i++)...
【标题】"hdu.rar_HDU 1089.cpp_OJ题求和_hdu_horsekw5_杭电obj" 提供的信息是关于一个压缩文件,其中包含了一个名为 "HDU 1089.cpp" 的源代码文件,这个文件是为了解决杭州电子科技大学(Hangzhou Dianzi ...
HDU1059的代码
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
hdu1001解题报告