2 shunfurh shunfurh 于 2017.01.01 15:02 提问

National Treasures

Description

The great hall of the national museum has been robbed few times recently. Everyone is now worried about the security of the treasures on display. To help secure the hall, the museum contracted with a private security company to provide additional guards to stay in the great hall and keep an eye on the ancient artifacts. The museum would like to hire the minimum number of additional guards so that the great hall is secured.
The great hall is represented as a two dimensional grid of R * C cells. Some cells are already occupied with the museum’s guards. All remaining cells are occupied by artifacts of different types (statues, sculptures, ... etc.) which can be replaced by new hired guards. For each artifact, few other cells in the hall are identified as critical points of the artifact depending on the artifact value, type of vault it is kept inside, and few other factors. In other words, if this artifact is going to stay in the hall then all of its critical points must have guards standing on them. A guard standing in a critical position of multiple artifacts can keep an eye on them all. A guard, however, can not stand in a cell which contains an artifact (instead, you may remove the artifact to allow the guard to stay there). Also you can not remove an artifact and leave the space free (you can only replace an artifact with a new hired guard).
Surveying all the artifacts in the great hall you figured out that the critical points of any artifact (marked by a ⊙) are always a subset of the 12 neighboring cells as shown in the grid below.
2 3

1 9 4
12 ⊙ 10

8 11 5
7 6

Accordingly, the type of an artifact can be specified as a non-negative integer where the i-th bit is 1 only if critical point number i from the picture above is a critical point of that artifact. For example an artifact of type 595 (in binary 1001010011) can be pictured as shown in the figure below. Note that bits are numbered from right to left (the right-most bit is bit number 1.) If a critical point of an artifact lies outside the hall grid then it is considered secure.
2

1

⊙ 10

5
7

You are given the layout of the great hall and are asked to find the minimum number of additional guards to hire such that all remaining artifacts are secured.
Input

Your program will be tested on one or more test cases. Each test case is specified using R+1 lines. The first line specifies two integers (1 ≤ R,C ≤ 50) which are the dimensions of the museum hall. The next R lines contain C integers separated by one or more spaces. The j-th integer of the i-th row is -1 if cell (i, j) already contains one of the museum’s guards, otherwise it contains an integer (0 ≤ T < 212) representing the type of the artifact in that cell.
The last line of the input file has two zeros.
Output

For each test case, print the following line:
k. G
Where k is the test case number (starting at one,) and G is the minimum number of additional guards to hire such that all remaining artifacts are secured.
Sample Input

1 3
512 -1 2048
2 3
512 2560 2048
512 2560 2048
0 0
Sample Output

  1. 0
  2. 2

1个回答

caozhy
caozhy   Ds   Rxr 2017.01.05 23:50
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
hdu3360National Treasures (最大匹配,拆点法)
National Treasures Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1038 Accepted Submission(s): 364 Problem Description The great hall of
hdu_3360 National Treasures 最小点覆盖
#include #include #include #include using namespace std; #define N 52 int dx[13]={-1,-2,-2,-1,1,2,2,1,-1,0,1,0}; int dy[13]={-2,-1,1,2,2,1,-1,-2,0,1,0,-1}; int edge[N][N]; vector g[N*N]; int linker[N*
hdu 3360 National Treasures
这道题向了我好久,看了题解也是一时没想通。 二分图的建模个人感觉挺不容易的,可能是刚学的原因吧~ 题意:大厅每个位置都有一个文物或者一个守卫,              文物是安全的前提是: 关键位置上必须有一个守卫,或者文物本身的位置上有一个守卫。             求保证每个文物是安全的守卫的最少数量。 分析:由于文物的关键位置在文物的马步或者相邻的位置上,所以此问题可看成二分
National Treasures 6.3.8
National Treasures Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 118    Accepted Submission(s): 60   Probl
pomelo(五) Tutorial 2 Treasures
pomelo(五) Tutorial 2 Treasures #Tutorial 2 -- Treasures ##描述 Treasures 游戏是从 LordOfPomelo 中抽取出来,去掉了大量的游戏逻辑,用以更好的展示 Pomelo 框架的用法以及运作机制。 Treasures 很简单,输入一个用户名后,会随机得到一个游戏角色,进入游戏场景。在游戏场景中地上会散落一些宝物,每个宝物
Borrowing treasures from the wealthy: deep transfer learning through selective joint fine-tuning
做一些笔记 2017_CVPR_Borrowing treasures from the wealthy: deep transfer learning through selective joint fine-tuning Introduction: 1. 如果用少量的数据训练深度网络,那么它的性能可能还不如传统方法。少量的数据并不能够展现出sample diversity,所
hdu 3360 National Treasures 二分匹配
题意:给出一个R*C的表,每个格子上标有值,-1表示已经有的保安,其他表示古董的价值,要看守一个古董就必须在1~12各个点上都有保安,求最少要雇的保安。            思路:建图,从图中可以发现古董和保安的位置相差一个奇数,所以我们可以将表格着色,白的为x部,黑的为Y部,古董和保安连一条边,求最小点覆盖。           代码:     #include #include #in
天天写算法之National Treasures
地址点击打开链接这个题目的问题,我一开始百思不得其解,后来反过来想了想,就是求最少的点,把所有的线都占有了,那么就是最小覆盖问题,最小覆盖=最大匹配,emmmmm:这个题,我有一个地方很不理解,我们原本就有警卫,那么原本的警卫是怎么处理的?感觉这样做,是直接忽略掉原本有的警卫,然后给出了最大覆盖,那么万一原本的警卫占据了一个有用的位置,那么岂不是没有考虑到?哦~,还是最大覆盖问题,你再给出的线里面...
powerdesigner生成mysql的脚本时为什么多一个national?
错误效果: 正常效果: 将national去掉 方法: 选中字段,然后选择MySQL这个tab,然后将National前面的复选框勾去掉。
National Instruments LabVIEW 2010注册机和激活图解
National Instruments LabVIEW 2010注册机和激活图解,绝对好用