POJ2375 Cow Ski Area 【强连通分量】+【DFS】

POJ2375 Cow Ski Area 【强连通分量】+【DFS】CowSkiAreaTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 2323 Accepted: 660DescriptionFarmerJohn’scousin,FarmerRon,wholivesinthemountainsof

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

Cow Ski Area
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 2323   Accepted: 660

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.

Source

题意:本题描述了一片滑雪场,并且规定奶牛从一个点只能向它相邻的并且高度不大于它的点运动,现在想要在某些点对之间加上缆车使得奶牛也可以从较低点到达较高点,问最少需要多少辆这样的缆车就可以使得奶牛可以从任意一个点运动到滑雪场的每个角落。

解:对于相邻的高度相同的点,实际上路线是双向的,所以它们构成了强连通,然后这道题可以找出所有强连通,于是就构成了一个DAG,然后答案就是max(入度为0的点,出度为0的点),特别的,当整幅图已经是强连通时答案为0.这题求强连通可以用DFS,省去不少麻烦。

#include <stdio.h>
#include <string.h>
#define maxn 502

int map[maxn][maxn], scc[maxn][maxn];
int sccNum, id, head[maxn * maxn], n, m;
bool in[maxn * maxn], out[maxn * maxn];
struct Node{
    int to, next;
} E[maxn * maxn << 2];

void addEdge(int u, int v)
{
    E[id].to = v;
    E[id].next = head[u];
    head[u] = id++;
}

void getMap(int n, int m)
{
    int i, j; id = 0;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j)
            scanf("%d", &map[i][j]);
}

void DFS(int x, int y)
{
    if(scc[x][y]) return;
    scc[x][y] = sccNum;    
    if(x + 1 <= n && map[x+1][y] == map[x][y]) DFS(x + 1, y);
    if(x - 1 >= 0 && map[x-1][y] == map[x][y]) DFS(x - 1, y);
    if(y + 1 <= m && map[x][y+1] == map[x][y]) DFS(x, y + 1);
    if(y - 1 >= 0 && map[x][y-1] == map[x][y]) DFS(x, y - 1);
}

void solve(int n, int m)
{
    memset(scc, 0, sizeof(scc));
    memset(in, 0, sizeof(in));
    memset(out, 0, sizeof(out));
    memset(head, -1, sizeof(head));
    sccNum = 0;
    int i, j, ans1 = 0, ans2 = 0;
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j)
            if(!scc[i][j]){
                ++sccNum; DFS(i, j);
            }
    for(i = 1; i <= n; ++i)
        for(j = 1; j <= m; ++j){
            if(i + 1 <= n && scc[i][j] != scc[i+1][j]){
                if(map[i][j] > map[i+1][j]){
                    addEdge(scc[i][j], scc[i+1][j]);
                    in[scc[i+1][j]] = out[scc[i][j]] = 1;
                } else{
                    addEdge(scc[i+1][j], scc[i][j]);
                    in[scc[i][j]] = out[scc[i+1][j]] = 1;
                }
            }
            if(j + 1 <= m && scc[i][j] != scc[i][j+1]){
                if(map[i][j] > map[i][j+1]){
                    addEdge(scc[i][j], scc[i][j+1]);
                    in[scc[i][j+1]] = out[scc[i][j]] = 1;
                } else{
                    addEdge(scc[i][j+1], scc[i][j]);
                    in[scc[i][j]] = out[scc[i][j+1]] = 1;
                }
            }
        }
    if(sccNum != 1)
        for(i = 1; i <= sccNum; ++i){
            if(!in[i]) ++ans1;
            if(!out[i]) ++ans2;
        }
    if(ans1 < ans2) ans1 = ans2;
    printf("%d\n", ans1);
}

int main()
{
    while(scanf("%d%d", &m, &n) == 2){
        getMap(n, m);
        solve(n, m);
    }
    return 0;
}

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

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

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

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

(0)


相关推荐

  • Python获取图像大小_如何读取0像素图片

    Python获取图像大小_如何读取0像素图片在一张图片中,我们可以获取它的宽和高的像素大小fromPILimportImageimage=Image.open(‘图片的路径’)imagePixmap=Image.size #宽高像素print(imagePixmap)但是在使用百度OCR进行文字识别的时候,文字识别的图片大小不能超过4M,在自动识别文字的时候,就避免不了读取图片的内存大小,如果是大于4M的话,要对图片进行压缩,下面是读取图片内存的代码:importosimagePath=os.path.joi

  • kubernetes CKA题库(附答案)

    kubernetes CKA题库(附答案)第一题RBAC授权问题权重:4%设置配置环境:[student@node-1]$kubectlconfiguse-contextk8sContext为部署管道创建一个新的ClusterRole并将其绑定到范围为特定的namespace的特定ServiceAccount.Task创建一个名为deployment-clusterrole且仅允许创建以下资源类型的新ClusterRole:DeploymentStatefulSetDaemonSet在现有的name

  • 互联网测试面试题及答案(软件测试面试题及答案2019)

    很多软件测试工程师在面试互联网企业的时候都会遇到考官给的几道面试题,这也反应了测试工程师对企业的重要性,今天传智播客整理了一份2019年的互联网企业软件测试面试题,希望能帮助到大家。2019年互联网企业软件测试面试题(常考)1、什么是兼容性测试?答:兼容性测试是检查软件在不同软件平台,硬件平台上是否可以正常运行的测试。主要查看软件在不同操作系统、浏览器、数据库中运行是否正常。2、你能不能…

  • Qt:windows下Qt安装教程

    Qt:windows下Qt安装教程win10按照qt

  • maven详细教程_maven的安装与配置

    maven详细教程_maven的安装与配置学习maven的使用,看到一篇很实用的入门教程(菜鸟级入门)2007-08-2814:01:04标签:maven职场休闲一、前言早就知道maven在java项目的管理方面名声显赫,于是就想着学习掌握之,于是查阅了大量文档。发现这些文档的作者都是java的大腕,大多都是站在掌握了一定maven基础的角度上进行介绍,让我这初学者看的云里雾里不…

  • svn更换服务器地址_如何登录svn服务器

    svn更换服务器地址_如何登录svn服务器描述本文适用于服务器镜像复制的情况,即svn在原本的服务器上,在服务器控制台上,将原本服务器的镜像导入新的服务器中,因此可能并不适用于所有的情况;操作步骤1.将快到期的服务器镜像进行导出,在新的服务器上进入镜像导入,等待完成即可;2.由于是镜像复制,因此原本的svn配置一致,只需要修改分支绑定的服务器域名即可,如下所示:查看迁移后的svn项目绑定的服务器信息将当前项目目录中的.svn目录进行删除(保险起见,可以先进行备份)#进入项目cd/dir…/larave

发表回复

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

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