如果能把杨大哥这段代码理解透彻 那么图论那一节应该有了个很好的认识

我也该睡了  大家晚安

我也利用这个机会好好学学吧。今天晚了，明天研究。

现在的 C 区感觉氛围好正呀，几位版主的功劳是莫大的。

问题找到了，就是最后答案求交集的问题。

思维不严谨啊，哎。

AC了，一开始的思路是对的，被我自己优化错了，NND。

#include<stdio.h>
#include<stdlib.h>

typedef struct node_struct
{
    int height;
    int signal;
}node;

int SIGNAL = 1;
int result = 0;
int perfect = 0;

void find_result(node *last, int n)
{
    int i;
    for (i=0; i<n; i++)
    if (0==last[i].signal) result++;
}

void find_perfect(int (*scope)[2], int j, int n)
{
    int start = -1, last = 0, i;
    while (last!=n)
    {
        for (i=0; i<j; i++)
        if (scope[i][0]<=start+1&&scope[i][1]>last) last = scope[i][1];
        start = last;
        perfect++;
    }
}

int find_target(node *line, int n)
{
    static int i = 0;
    if (1==n)
    {
        if (0==line[0].signal) return 0;
        else return -1;
    }
    for (; i<n; i++)
    {
        if (0==line[i].signal)
        {
            if (i==0)
            {
                if (line[i].height>=line[i+1].height) return i;
            }
            else if (i==n-1)
            {
                if (line[i].height>=line[i-1].height) return i;
            }
            else if (line[i].height>=line[i-1].height&&line[i].height>=line[i+1].height)
                return i;
        }
    }
    return -1;
}

void find_answer(node *store, int id, int m, int n)
{
    int i = id/n, j = id%n;
    if (store[id].signal == SIGNAL) return;
    store[id].signal = SIGNAL;
    if (i!=m-1&&store[id].height>store[id+n].height) find_answer(store, id+n, m, n);
    if (j!=n-1&&store[id].height>store[id+1].height) find_answer(store, id+1, m, n);
    if (j!=0&&store[id].height>store[id-1].height) find_answer(store, id-1, m, n);
    if (i!=0&&store[id].height>store[id-n].height) find_answer(store, id-n, m, n);
}

int main()
{
    int M, N, i=0, j=0, k=0, t, (*scope)[2], flag=0;
    node *store, *last;
    scanf("%d%d",&M,&N);
    store = (node *)malloc(M*N*sizeof(node));
    scope = (int (*)[2])malloc(sizeof(int)*2*N);
    for (t=M*N,i=0; i<t; i++) store[i].signal = 0,scanf("%d",&store[i].height);
    last = store+(M-1)*N;
    for (i=find_target(store,N); i>=0; i=find_target(store,N))
    {
        find_answer(store,i,M,N);
        for (flag=0,k=0; k<N; k++)
        {
            if (flag==0&&last[k].signal==SIGNAL) flag=1, scope[j][0] = k;
            if (flag==1&&last[k].signal!=SIGNAL) 
            {
                scope[j][1] = k-1;
                break;
            }
            else if (flag==1&&k==N-1)
            scope [j][1] = N-1;
        }
        j++, SIGNAL++;
    }
    find_result(last,N);
    free(store);
    if (result>0)
    {
        printf("%d\n%d\n",0,result);
        return 0;
    }
    find_perfect(scope,j,N-1);
    printf("%d\n%d\n",1,perfect);
    return 0;
}

这难道说明我的成绩比杨大哥的还优秀？

暗喜中。。。。

呵呵，10毫秒是它系统的时间片分配单位，这10毫秒是存在误差的。我第二次提交的代码仅仅是将LEN宏由600改成500，减少多余的空间占用，结果提交时间却多出了10毫秒。你可以再提交一次看看是否还稳定在190毫秒。

10毫秒的差距，算法上没什么差别，差别在代码级的优化上。

不过快了就是快了，你的成绩比我的好。如果有兴趣在这方面PK，我可以优化一下我的代码。

跟你PK我果断虚了…

加上键盘赋值函数了：

#include "stdio.h"
#define LEN  50
int a[LEN][LEN],b[LEN][LEN],d[LEN][LEN];
int r,c,bj=0;
void f6(){
    int i,j;
    printf("\ninput num of row:");
    scanf("%d",&r);
    printf("\ninput num of column:");
    scanf("%d",&c);
    if(r>LEN)r=LEN;if(c>LEN)c=LEN;
    printf("\ninput data:\n");
    for(i=0;i<r;i++)
        for(j=0;j<c;j++){
            scanf("%d",&a[i][j]);
            b[i][j]=0;d[i][j]=0;
        }
}
void f1(int i,int j){
    int k;
    b[i][j]=1;
    for(k=j;k<c-1;k++)
        if(a[i][k]>a[i][k+1]&&b[i][k+1]==0)f1(i,k+1);
        else break;
    for(k=i;k<r-1;k++)
        if(a[k][j]>a[k+1][j]&&b[k+1][j]==0)f1(k+1,j);
        else break;
    for(k=j;k>0;k--)
        if(a[i][k]>a[i][k-1]&&b[i][k-1]==0)f1(i,k-1);
        else break;
    for(k=i;k>0;k--)
        if(a[k][j]>a[k-1][j]&&b[k-1][j]==0)f1(k-1,j);
}
void f2(int k,int n){
    int i,j,m;
    for(i=k;i<c&&bj==0;i++){
        for(j=0;j<c;j++)b[r-1][j]=b[r-1][j]+d[i][j];
        if(n>1)f2(i+1,n-1);
        else{
            for(j=0;j<c;j++)if(b[r-1][j]==0)break;
            if(j==c)bj=1;
        }
        for(j=0;j<c;j++)b[r-1][j]=b[r-1][j]-d[i][j];
    }
}
void f5(){
    int i,j,k;
    for(i=0;i<r;i++)
        for(j=0;j<c;j++)
            b[i][j]=0;
}
void main(){
    int i,j,m=0;
    clrscr();
    f6();
    for(j=0;j<c;j++){
        f1(0,j);
        for(i=0;i<c;i++)d[j][i]=b[r-1][i];
        f5();
    }
    printf("\nout:\n");
    for(j=1;j<=c;j++){
        f2(0,j);
        if(bj==1){
            printf("%d\n%d",1,j);
            break;
        }
    }
    if(j>c){
        for(i=0;i<c;i++){
            b[r-1][i]=0;
            for(j=0;j<c;j++)
                b[r-1][i]=b[r-1][i]+d[j][i];
            if(b[r-1][i]==0)m=m+1;
        }
        printf("%d \n%d",0,m);
    }
}

呵呵，看来我的气场还不错。有竞争进步才快，正当的竞争是一种动力。不过这道题我觉得没什么发掘价值了。

有没有兴趣再召集几个志同道合的兄弟，咱们找个学校的OJ组团刷题去？

很久没玩ACM了，我一直想把某个学校的题全A掉。