加载中…
个人资料
abentu
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

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

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

      

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

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有