poj 2375「建议收藏」

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

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

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

        不过在做这道时，开始想通过一次搜索来完成所有强连通分量的标记，不过有些问题一直无法解决，无奈只好多次广搜，每次找一个强连通分量。找到强连通分量，接下来的做法就和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）：

Description

Input

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