注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[nbut] 1187 Hole Breaker  

2012-11-08 20:58:34|  分类: NBUT OJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
 

     这几天在切回NOJ的题目了。先放出两道差不多的题目。

     题目链接:http://acm.nbut.cn/Problem/view.xhtml?id=1187

    这道题的意思是挖洞,求最大连通块。

    先分析一下样例输入输出:

   样例输入
   3 5     //一幅3×3的图,有5个问题
   B 0 0       //B为挖洞指令,即在(0,0)处挖洞
   C           //C为输出指令,即输出这时的最大连通块的大小
   B 1 0
   B 2 2
  C
  样例输出
  1
  2

一般来说先想到用DFS,但是这道题的数据 (N <= 3 <= 1000, 1 <= M <= 200000)用DFS肯定超时。那么这时

我们就考虑用并查集。

 代码如下:

 

 

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define Max 1000
int map[Max][Max];
int father[Max * Max],rank[Max * Max];
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int Maxn;
int flag;
int Find(int x)
{
    if(father[x] == x)   return x;
    else
 {
  father[x] = Find(father[x]);
  return father[x];
 }
}

void Union( int x, int y)
{
  int xx = Find(x);
  int yy = Find(y);
  if(xx != yy)
  {
   rank[xx] += rank[yy];
   father[yy] = xx;
   if(rank[xx] > Maxn)
    Maxn = rank[xx];
  }
}

void Chu(int n)
{
  for(int i = 0;i < n * n;i++)
  {
     father[i] = i;
     rank[i] = 1;
   }
}

int main()
{
   int n,m;
   while(~scanf("%d%d",&n,&m))
   {
      Maxn = 1;flag = 0;
     Chu(n);
      memset(map,0,sizeof(map));
      for(int j = 0;j < m;j ++)
      {
        char c;
        getchar();
        scanf("%c",&c);
        if(c == 'B')
        {
         flag = 1;
            int x,y;   scanf("%d%d",&x,&y);
            map[x][y] = 1;
            for(int i = 0;i < 4;i ++)
            {
                int xx = x + dir[i][0];
                int yy = y + dir[i][1];
                if(xx >= n || yy >= n || xx < 0 || yy < 0) continue;
                if(map[xx][yy] == 1)
                   Union(x * n + y,xx * n + yy);
            }
       }
       else
       {
        if(flag == 0) printf("0\n");
           else printf("%d\n",Maxn);
       }
     }
  }
}

//样例输入
//
//3 5
//B 0 0
//C
//B 1 0
//B 2 2
//C
//
//样例输出
//
//1
//2


 

 

 


 

  评论这张
 
阅读(102)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018