首页 > 其他 > 详细

2014 UESTC Training for Data Structures A - Islands

时间:2014-04-30 23:39:39      阅读:635      评论:0      收藏:0      [点我收藏+]

A - Islands

Time Limit: 30000/10000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
 

Deep in the Carribean, there is an island even stranger than the Monkey Island, dwelled by Horatio Torquemada Marley. Not only it has a rectangular shape, but is also divided into an n×m grid. Each grid field has a certain height. Unfortunately, the sea level started to raise and in year i, the level is i meters. Another strange feature of the island is that it is made of sponge, and the water can freely flow through it. Thus, a grid field whose height is at most the current sea level is considered flooded.Adjacent unflooded fields (i.e., sharing common edge) create unflooded areas. Sailors are interested in the number of unflooded areas in a given year.

An example of a 4×5 island is given below. Numbers denote the heights of respective fields in meters.Unflooded fields are darker; there are two unflooded areas in the first year and three areas in the second year.

bubuko.com,布布扣

Input

Multiple Test Cases

The input contains several test cases. The first line of the input contains a positive integer Z20,denoting the number of test cases. Then Z test cases follow, each conforming to the format described in section Single Instance Input. For each test case, your program has to write an output conforming to the format described in section Single Instance Output.

Single Instance Input

The first line contains two numbers n and m separated by a single space, the dimensions of the island, where 1n,m1000. Next n lines contain m integers from the range [1,109] separated by single spaces, denoting the heights of the respective fields. Next line contains an integer T (1T105). The last line contains Tintegers tj , separated by single spaces, such that 0t1t2?tT109

Output

Single Instance Output

Your program should output a single line consisting of T numbers rj , where rj is the number of unflooded areas in year tj . After every number ,you must output a single space!

Sample input and output

Sample Input Sample Output
1
4 5
1 2 3 3 1
1 3 2 2 1
2 1 3 4 3
1 2 2 2 2
5
1 2 3 4 5
2 3 1 0 0

 

题意就是有一个矩阵,求第i天矩阵中大于i的部分连通块的个数。

题目会给出i,i是递增的,所以可以从最后一天做起,每天被昨天淹没且不被今天淹没的大陆浮起来,并将其与已经浮起来的大陆连接起来,再求连通块的个数。连接这里需要用到并查集,而由于i最大是10^9,但i的询问个数不超过10000,所以要离散化。

这道题还有个坑就是时间限制居然是10s,一开始怎么想都是超时=。=

 

bubuko.com,布布扣
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
int q[1005][1005];
vector<int> w;
vector<int> x[100005];
int found[1005][1005];
int father[1005][1005];
int hang,lie,ans;
int Rank[1100005]={};
int getfather(int j,int k)
{
    if (father[j][k]!=j*1000+k-1)
        father[j][k]=getfather(father[j][k]/1000,father[j][k]%1000+1);
    return father[j][k];
}
void judge(int g,int h,int j,int k)
{
    int fx,fy;
    if ((fx=getfather(g,h))==(fy=getfather(j,k))) return ;
    ans--;
    if (Rank[fx]>Rank[fy]) father[fy/1000][fy%1000+1]=fx;
    else{
            father[fx/1000][fx%1000+1]=fy;
            if (Rank[fx]==Rank[fy])
                Rank[fx]++;
        }
    return;
}
void dfs(int g,int h)
{
    if (found[g][h]) return;
    found[g][h]++;
    ans++;
    if (found[g+1][h] && g<hang) judge(g,h,g+1,h);
    if (found[g-1][h] && g>1) judge(g,h,g-1,h);
    if (found[g][h+1] && h<lie) judge(g,h,g,h+1);
    if (found[g][h-1] && h>1) judge(g,h,g,h-1);
    return ;
}
int main()
{
    int g,h,j,k,l,n,T;
    cin>>T;
    while (T--){
        memset(found,0,sizeof(found));
        cin>>g>>h;
        memset(q,0,sizeof(q));
        for (j=1;j<=g;j++)
            for(k=1;k<=h;k++)
                scanf("%d",&q[j][k]);
        cin>>l;
        hang=g;
        lie=h;
        for (j=1;j<=g;j++) for (k=1;k<=h;k++) father[j][k]=j*1000+k-1;
        ans=0;
        memset(Rank,0,sizeof(Rank));
        vector <int>().swap(w);
        for (j=0;j<100005;j++) vector <int>().swap(x[j]);
        w.push_back(0);
        for (j=1;j<=l;j++){
            scanf("%d",&n);
            w.push_back(n);
        }
        w.push_back(1000000007);
        for (j=1;j<=g;j++)
            for(k=1;k<=h;k++)
                q[j][k]=lower_bound(w.begin(),w.end(),q[j][k])-w.begin();
        for (j=1;j<=g;j++)
            for (k=1;k<=h;k++)
                if (q[j][k]>=0) x[q[j][k]].push_back(j*1000+k-1);
        for (j=w.size()-2;j>0;j--){
            for (int k=0;k<x[j+1].size();k++)
                dfs((int)x[j+1][k]/1000,(int)x[j+1][k]%1000+1);
            w[j]=ans;
        }
        for (j=1;j<w.size()-1;j++) printf("%d ",w[j]);
        cout<<endl;
    }
    return 0;
}
bubuko.com,布布扣

这道题代码不是很长,我居然前后用了6个小时才AC,看来是我太弱了。。。。。

2014 UESTC Training for Data Structures A - Islands,布布扣,bubuko.com

2014 UESTC Training for Data Structures A - Islands

原文:http://www.cnblogs.com/Atlantis67/p/3701189.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!