大家好，又见面了，我是你们的朋友全栈君。
这道题是一道关于强连通分量的题目，不过这道题给出的图比较特殊，所以在求强连通分量时，可以采用广搜来做。
这道强连通分量的题，给出的图十分特殊，如果在上下、左右四个方向相邻的区域，如果高度相同，则是相互可达的，所以我们可以通过搜索找出强连通分量，可以降低时间复杂度。
不过在做这道时，开始想通过一次搜索来完成所有强连通分量的标记，不过有些问题一直无法解决，无奈只好多次广搜，每次找一个强连通分量。找到强连通分量，接下来的做法就和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）：
| Time Limit: 1000MS | Memory Limit: 65536K | |
Description
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
* Lines 2..L+1: L lines, each with W space-separated integers corresponding to the height of each square of land.
Output
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
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.
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/130774.html原文链接：https://javaforall.net
