poj 2375

poj 2375这道题是一道gu

大家好,又见面了,我是你们的朋友全栈君。

        这道题是一道关于强连通分量的题目,不过这道题给出的图比较特殊,所以在求强连通分量时,可以采用广搜来做。

        这道强连通分量的题,给出的图十分特殊,如果在上下、左右四个方向相邻的区域,如果高度相同,则是相互可达的,所以我们可以通过搜索找出强连通分量,可以降低时间复杂度。

        不过在做这道时,开始想通过一次搜索来完成所有强连通分量的标记,不过有些问题一直无法解决,无奈只好多次广搜,每次找一个强连通分量。找到强连通分量,接下来的做法就和poj 1236(http://blog.csdn.net/u011008379/article/details/37995979)中的第二问做法一样了,这里就不多解释。

        代码(C++):

#include <cstdlib>
#include <iostream>
#include <algorithm>

#define MAX 509
using namespace std;

//#define LOCAL

typedef pair<int,int> pii;

int map[MAX][MAX],dir[][2]={
  
  {0,-1},{1,0},{0,1},{-1,0}},id[MAX][MAX],vis[MAX][MAX],odeg[MAX*MAX],ideg[MAX*MAX];
int p,s,n,m;
pii queue[MAX*MAX];

void bfs(int u,int v,int c)
{
     int a,b,i;
     pii tmp;
     
     p=s=0;
     id[u][v]=c;
     queue[p++]=make_pair(u,v);
     vis[u][v]=true; 
        
     while(s<p)
     {
         tmp=queue[s++];
         for(i=0;i<4;i++)
         {
             a=dir[i][1]+tmp.first;
             b=dir[i][0]+tmp.second;
                                  
             if(a>=0&&a<n&&b>=0&&b<m&&map[a][b]==map[tmp.first][tmp.second])
             {
                   if(vis[a][b]) continue;
                   id[a][b]=c;                               
                   queue[p++]=make_pair(a,b);  
                   vis[a][b]=true;                 
             }            
         }                    
     }
}

int main(int argc, char *argv[])
{
#ifdef LOCAL
   freopen("in.txt","r",stdin);
   freopen("out.txt","w",stdout);
#endif
    int i,j,k,x,y,a,b,c;
    while(scanf("%d %d",&m,&n)!=EOF)
    {
         for(i=0;i<n;i++)
         {
            for(j=0;j<m;j++)
            {
                scanf("%d",&map[i][j]);            
            }             
         }
         
         c=0;                 
         memset(vis,false,sizeof(vis));
         memset(id,-1,sizeof(id));
         for(i=0;i<n;i++)
         {
             for(j=0;j<m;j++)
             {
                 if(!vis[i][j]) bfs(i,j,c++);            
             }            
         }
         if(c==1)
         {
             printf("0\n");    
         }else{
             memset(ideg,0,sizeof(ideg));
             memset(odeg,0,sizeof(odeg));
             for(i=0;i<n;i++)
             {
                 for(j=0;j<m;j++)
                 {
                     for(k=0;k<4;k++)
                     {
                        a=dir[k][1]+i;
                        b=dir[k][0]+j;
                        if(a>=0&&a<n&&b>=0&&b<m)
                        {
                             if(id[i][j]!=id[a][b]) 
                             {
                                 if(map[i][j]>map[a][b])
                                 {
                                     odeg[id[i][j]]++;
                                     ideg[id[a][b]]++;                    
                                 }else{
                                    odeg[id[a][b]]++;
                                    ideg[id[i][j]]++;  
                                 }                   
                             }                    
                        }            
                     }           
                 }             
             }
             x=y=0;
             for(i=0;i<c;i++)
             {
                if(odeg[i]==0) x++;
                if(ideg[i]==0) y++;            
             }
             printf("%d\n",max(x,y));
         }          
    }
    system("PAUSE");
    return EXIT_SUCCESS;
}

题目(
http://poj.org/problem?id=2375):

Cow Ski Area
Time Limit: 1000MS   Memory Limit: 65536K
     

Description

Farmer John’s cousin, Farmer Ron, who lives in the mountains of Colorado, has recently taught his cows to ski. Unfortunately, his cows are somewhat timid and are afraid to ski among crowds of people at the local resorts, so FR has decided to construct his own private ski area behind his farm. 

FR’s ski area is a rectangle of width W and length L of ‘land squares’ (1 <= W <= 500; 1 <= L <= 500). Each land square is an integral height H above sea level (0 <= H <= 9,999). Cows can ski horizontally and vertically between any two adjacent land squares, but never diagonally. Cows can ski from a higher square to a lower square but not the other way and they can ski either direction between two adjacent squares of the same height. 

FR wants to build his ski area so that his cows can travel between any two squares by a combination of skiing (as described above) and ski lifts. A ski lift can be built between any two squares of the ski area, regardless of height. Ski lifts are bidirectional. Ski lifts can cross over each other since they can be built at varying heights above the ground, and multiple ski lifts can begin or end at the same square. Since ski lifts are expensive to build, FR wants to minimize the number of ski lifts he has to build to allow his cows to travel between all squares of his ski area. 

Find the minimum number of ski lifts required to ensure the cows can travel from any square to any other square via a combination of skiing and lifts.

Input

* Line 1: Two space-separated integers: W and L 

* Lines 2..L+1: L lines, each with W space-separated integers corresponding to the height of each square of land.

Output

* Line 1: A single integer equal to the minimal number of ski lifts FR needs to build to ensure that his cows can travel from any square to any other square via a combination of skiing and ski lifts

Sample Input

9 3
1 1 1 2 2 2 1 1 1
1 2 1 2 3 2 1 2 1
1 1 1 2 2 2 1 1 1

Sample Output

3

Hint

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed. 

OUTPUT DETAILS: 

FR builds the three lifts. Using (1, 1) as the lower-left corner, 

the lifts are (3, 1) <-> (8, 2), (7, 3) <-> (5, 2), and (1, 3) <-> 

(2, 2). All locations are now connected. For example, a cow wishing 

to travel from (9, 1) to (2, 2) would ski (9, 1) -> (8, 1) -> (7, 

1) -> (7, 2) -> (7, 3), take the lift from (7, 3) -> (5, 2), ski 

(5, 2) -> (4, 2) -> (3, 2) -> (3, 3) -> (2, 3) -> (1, 3), and then 

take the lift from (1, 3) – > (2, 2). There is no solution using 

fewer than three lifts.

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/130776.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • intellij idea 控制台中文乱码_idea server控制台乱码

    intellij idea 控制台中文乱码_idea server控制台乱码本人下载了一开源工程,该工程采用的是maven进行编译,在导入到itellijidea后,按如下图配置好maven编译环境但是采用配置好的maven进行编译时,在run的控制台输出窗口中出现乱码,导致无法编译,由于工程是utf-8编码,所以按如下方式配置了工程的编码网上run控制台输出乱码的解决思路如下:1)参照上面配置工程编码的方式将GlobalEncoding/Proj…

  • Java动态代理机制详解(JDK 和CGLIB,Javassist,ASM)「建议收藏」

    Java动态代理机制详解(JDK 和CGLIB,Javassist,ASM)「建议收藏」本文阐述:class文件和代码中的class对象之间的关系;动态代理中InvocationHandler角色的由来;Javassist和ASM框架生成字节码;类加载器

  • VS2013注册码_vs注册密钥

    VS2013注册码_vs注册密钥vs2012注册码YKCW6-BPFPF-BT8C9-7DCTH-QXGWCRBCXF-CVBGR-382MK-DFHJ4-C69G8MMVJ9-FKY74-W449Y-RB79G-8GJGJ4D974-9QX42-9Y43G-YJ7JG-JDYBPYCFHQ-9DWCY-DKV88-T2TMH-G7BHP亲测有效!

  • Linux 多学习过程

    Linux 多学习过程

  • Pytorch的BatchNorm层使用中容易出现的问题

    Pytorch的BatchNorm层使用中容易出现的问题前言:本文主要介绍在pytorch中的BatchNormalization的使用以及在其中容易出现的各种小问题,本来此文应该归属于[1]中的,但是考虑到此文的篇幅可能会比较大,因此独立成篇,希望能够帮助到各位读者。如有谬误,请联系指出,如需转载,请注明出处,谢谢。∇\nabla∇联系方式:e-mail:FesianXu@163.comQQ:973926198github:htt…

  • MPEG-4、MPEG-4/AVC、H.264之间的联系与区别「建议收藏」

    MPEG-4、MPEG-4/AVC、H.264之间的联系与区别「建议收藏」当你在网上下载视频时,经常会看到MPEG-4、h.264等等词汇,它们之间有什么关系吗?  在视频编解码技术定义方面有两大标准机构。一个是国际电信联盟(ITU)致力于电信应用,已经开发了用于低比特率视频电话的H.26x标准,其中包括H.261、H.262、H.263与 H.264;另一个是国际标准化组织(ISO)主要针对消费类应用,已经针对运动图像压缩定义了MPEG

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号