/* THE PROGRAM IS MADE BY PYY */
/*----------------------------------------------------------------------------//
Copyright (c) 2011 panyanyany All rights reserved.
URL : http://poj.org/problem?id=3020
Name : 3020 Antenna Placement
Date : Thursday, December 8, 2011
Time Stage : one hour
Result:
9644820 panyanyany
3020
Accepted 184K 0MS C++
1588B 2011-12-08 20:31:01
Test Data :
Review :
不知道为什么是最小路径覆盖(也有一种说法是最大独立集),不理解,求大牛指点….
我看到很多人是把它转化为一个标准的二分图来做的……这其实也是一种思路,不过我觉得
那样有点麻烦,就没有去做……貌似也是因为我没有想到这样做……
//----------------------------------------------------------------------------*/
#include <stdio.h>
#include <string.h>
#define MAXSIZE 43
struct POINT {
int x, y ;
};
int n, h, w ;
bool cover[MAXSIZE][MAXSIZE] ;
char map[MAXSIZE][MAXSIZE] ;
char dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1} ;
POINT link[MAXSIZE][MAXSIZE] ;
bool find (int py, int px)
{
int i, j ;
int x, y ;
for (i = 0 ; i < 4 ; ++i)
{
y = py + dir[i][0] ;
x = px + dir[i][1] ;
if ((0 < x && x <= w && 0 < y && y <= h) &&
!cover[y][x] &&
(map[y][x] == '*'))
{
cover[y][x] = true ;
if (!link[y][x].x || find (link[y][x].y, link[y][x].x))
{
link[y][x].y = py ;
link[y][x].x = px ;
return true ;
}
}
}
return false ;
}
int main ()
{
int i, j ;
int x, y ;
int sum, cnt ;
while (~scanf ("%d", &n))
{
while (n--)
{
scanf ("%d%d", &h, &w) ;
for (j = 1 ; j <= h ; j++)
{
scanf ("%s", &map[j][1]) ;
}
sum = cnt = 0 ;
memset (link, 0, sizeof (link)) ;
for (j = 1 ; j <= h ; ++j)
for (i = 1 ; i <= w ; ++i)
{
if (map[j][i] == '*')
{
++ cnt ;
memset (cover, 0, sizeof (cover)) ;
sum += find (j, i) ;
}
}
printf ("%d\n", cnt - sum / 2) ;
}
}
return 0 ;
}
分享到:
相关推荐
北大POJ3020-Antenna Placement 解题报告+AC代码
北大POJ经典结题报告 北大POJ经典结题报告 北大POJ经典结题报告 注重方法,内容详尽,物超所值
很多的POJ题目答案!1000~1008,1011~1014,1016,1017,1019,1028,1032,1045,1046,1047,1050,1061,1067,1068,1088,1102,1159,1163,1183,1207,1218,1226,1247,1256,1258,1298,1316,1323,...
初期: 一.基本算法: (1)枚举. (poj1753,poj2965) (2)贪心(poj1328,poj2109,poj2586) ... (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) (6)最大流的增广路算法(KM算法). (poj1459,poj3436) ......
如果你为在poj上找不到解题思路而痛苦,那么这本书可以为你带来惊喜,里面包括了poj上一部分题解题报告~
各种搜索算法,配合POJ上的题目,含标程,及各题解题思路。
北大POJ初级-图算法 解题报告+AC代码
ACM POJ 解题报告北大POJ 大量解题代码
北大POJ初级题-数据结构:解题报告+AC代码
北大poj解题报告,希望能帮到软件工程的同学,每天一道,持之以恒,熟能生巧,与您共勉!
北大POJ1159-Palindrome
北大POJ1837-Balance
NULL 博文链接:https://128kj.iteye.com/blog/1772172
北大poj JAVA源码
北大POJ初级-所有题目AC代码+解题报告
北大POJ第1005题答案(C语言)
北大POJ初级-简单搜索 解题报告+AC代码
北大POJ第1324题(C++)
北大POJ200多道程序解答 完整代码 供大家参考 相互切磋
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习