# 加载中...

abentu
• 博客等级：
• 博客积分：0
• 博客访问：15,882
• 关注人气：4
• 获赠金笔：0支
• 赠出金笔：0支
• 荣誉徽章：

## poj1652-Holey Cloth

(2010-07-15 13:47:41)

### 杂谈

在一个布料组成的地图中找到洞洞最多的布料，如果有相同则取布料面积最小的，输出这个布料的面积。

首先理解题意需要下一些功夫，我是这样理解的，布料之间没有连接的话则他们是相互分离的，而他们各自洞的大小不与其他布料有任何关系，也就是说算布料a的洞的时候就可以把布料bcd都看做是没有这个不了或者全是空挡即可。

分层广搜，先找出来每一种布料统计面积，然后再对每一个布料广搜得到洞洞的个数即可。

我写得比较粗心所以调了很久。

#include "iostream"
#include "stdio.h"
#include "memory.h"
using std::cin;
#define N 110
#define M 12100

const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};

bool graph[N][N],judge[N][N];
int map[N][N];

int queue[M][2],l,r;

int area[M];
int hole[M];
int w,h,m;

int main()
{
freopen("3.txt","r",stdin);

memset(graph,0,sizeof(graph));
memset(map,0,sizeof(map));

scanf("%d%d",&w,&h);

int i,j,ii,jj,xx,yy;
char c;

while (cin.peek() != '.' && cin.peek() != '*')
cin.ignore();
for (i = 1;i <= h;i ++)
{
for (j = 1;j <= w;j ++)
{
scanf("%c",&c);
if (c == '*')
graph[i][j] = 1;
else
graph[i][j] = 0;
}
if (i < h)
{
while (cin.peek() != '.' && cin.peek() != '*')
cin.ignore();
}
}
for (i = 1;i <= 100;i ++)
for (j = 1;j <= 100;j ++)
if (graph[i][j] != 1)
graph[i][j] = 0;
h = 100;
w = 100;

m = 0;

memset(area,0,sizeof(area));

for (i = 1;i <= h;i ++)
{
for (j = 1;j <= w;j ++)
if (graph[i][j] == 1 && map[i][j] == 0)
{
m ++;

memset(queue,0,sizeof(queue));
l = 1;
r = 1;
queue[r][0] = i;
queue[r][1] = j;
map[i][j] = m;
area[m] = 1;

while (l <= r)
{
xx = queue[l][0];
yy = queue[l][1];
l ++;

for (ii = 0;ii <= 3;ii ++)
{
if (xx+dx[ii] >= 1 && xx+dx[ii] <= h && yy+dy[ii] >= 1 && yy+dy[ii] <= w )
if( graph[xx+dx[ii]][yy+dy[ii]] == 1 && map[xx+dx[ii]][yy+dy[ii]] == 0)
{
r ++;
queue[r][0] = xx+dx[ii];
queue[r][1] = yy+dy[ii];
map[xx+dx[ii]][yy+dy[ii]] = m;
area[m] ++;
}
}
}
}
}

memset(hole,0,sizeof(hole));

for (ii = 1;ii <= m;ii ++)
{
memset(judge,0,sizeof(judge));

for (i = 0;i <= h + 1;i ++)
for (j = 0;j <= w + 1;j ++)
if (map[i][j] != ii && judge[i][j] == 0)
{
hole[ii] ++;

memset(queue,0,sizeof(queue));

l = 1;
r = 1;
queue[r][0] = i;
queue[r][1] = j;
judge[i][j] = 1;

while (l <= r)
{
xx = queue[l][0];
yy = queue[l][1];
l ++;

for (jj = 0;jj <= 3;jj ++)
{
if (xx + dx[jj] >= 0 && xx + dx[jj] <= h+1 && yy + dy[jj] >= 0 && yy + dy[jj] <= w+1)
if (map[xx+dx[jj]][yy+dy[jj]] != ii && judge[xx+dx[jj]][yy+dy[jj]] == 0)
{
r ++;
queue[r][0] = xx + dx[jj];
queue[r][1] = yy + dy[jj];
judge[xx+dx[jj]][yy+dy[jj]] = 1;
}
}
}
}

hole[ii]--;

}

int max = -1,result = 0;

for (i = 1;i <= m;i ++)
{
if (hole[i] > max)
{
max = hole[i];
result = i;
}
else if (hole[i] == max && area[i] < area[result])
{
result = i;
}
}

if (result == 0 || max == 0)
{
printf("0\n");
return 0;
}

printf("%d\n",area[result]);

return 0;
}

0

• 评论加载中，请稍候...

发评论

以上网友发言只代表其个人观点，不代表新浪网的观点或立场。

新浪BLOG意见反馈留言板　电话：4000520066 提示音后按1键（按当地市话标准计费）　欢迎批评指正

新浪公司 版权所有