poj 2375 Cow Ski Area bfs

這個題目用tarjan找聯通塊，縮點，然後統計出入度為0的點理論上是可行的，但問題是會暴棧。考慮到這個題目的特殊性，可以直接用一次bfs找到數字相同且聯通的塊，這就是一個聯通塊，然後縮點，統計出入度即可。

 
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cmath>  
using namespace std;  
const int maxn=1e3+9;  
int a[maxn][maxn];  
int con;  
int ss[maxn*maxn],in[maxn*maxn],out[maxn*maxn];  
int n,m;  
struct  
{  
    int t,s;  
}que[maxn*maxn];  
bool text[maxn*maxn];  
void bfs()  
{  
    con=0;  
    memset(text,0,sizeof(text));  
    for(int i=1;i<=n;i++)  
    for(int j=1;j<=m;j++)  
    if(!text[i*m+j])  
    {  
        int front=1,end=0;  
        que[++end].t=i;  
        que[end].s=j;  
        text[i*m+j]=1;  
        while(front<=end)  
        {  
            int t=que[front].t,s=que[front++].s;  
            for(int p=-1;p<=1;p++)  
            for(int q=-1;q<=1;q++)  
            if(fabs(p)+fabs(q)==1&&t+p>=1&&t+p<=n&&s+q>=1&&s+q<=m)  
            if(a[t][s]==a[t+p][s+q])  
            if(!text[(t+p)*m+s+q])  
            {  
                text[(t+p)*m+s+q]=1;  
                que[++end].t=t+p;  
                que[end].s=s+q;  
            }  
        }  
        con++;  
        for(int i=1;i<=end;i++)  
        {  
            ss[que[i].t*m+que[i].s]=con;  
        }  
    }  
}  
  
int main()  
{  
//    freopen("in.txt","r",stdin);  
    while(scanf("%d %d",&m,&n)!=EOF)  
    {  
        for(int i=1;i<=n;i++)  
        for(int j=1;j<=m;j++)  
        scanf("%d",&a[i][j]);  
        bfs();  
        memset(in,0,sizeof(in));  
        memset(out,0,sizeof(out));  
        for(int i=1;i<=n;i++)  
        for(int j=1;j<=m;j++)  
        for(int p=-1;p<=1;p++)  
        for(int q=-1;q<=1;q++)  
        if(fabs(p)+fabs(q)==1&&i+p>=1&&i+p<=n&&j+q>=1&&j+q<=m)  
        if(a[i][j]>=a[i+p][j+q])  
        if(ss[(i+p)*m+j+q]!=ss[i*m+j])  
        {  
            in[ss[(i+p)*m+j+q]]++;  
            out[ss[i*m+j]]++;  
        }  
        int ansin=0,ansout=0,ans;  
        for(int i=1;i<=con;i++)  
        {  
            if(in[i]==0)  
            ansin++;  
            if(out[i]==0)  
            ansout++;  
        }  
        ans=max(ansin,ansout);  
        if(con<=1)  
        printf("0\n");  
        else  
        printf("%d\n",ans);  
    }  
    return 0;  
}