你的这个算法很优啊！

按14楼的思路，写了一个代码，大家可以试一下：

#include "stdio.h"
int a[3][6]={{8,4,5,6,4,4},{7,3,4,3,3,3},{3,2,2,1,1,2}};
int b[3][6]={{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0}};
int d[6][6]={{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0}};
int r=3,c=6,bj=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);
        else break;
}
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();
    for(j=0;j<c;j++){
        f1(0,j);
        for(i=0;i<c;i++)d[j][i]=b[r-1][i];
        f5();
    }
    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);
    }
    getch();
}

[ 本帖最后由 netlin 于 2012-8-19 10:02 编辑 ]

楼上很强大，望尘莫及啊
请问一下，我也按照14楼思路写了，但统计出每个沿海城市能到达的沙漠城市后
是怎么做优化的，思路是什么，代码全是for循环看不懂啊

优化，用的是15楼的思路。

呵呵，时间到了。小施，是你先发代码还是我先发？


先点评一下15楼a745043791的代码吧。

这位朋友在开头已经说了那么多谦虚的话，那我也不好再严厉地批评了，只劝一句，代码写完不算完，一定要看看执行的对不对。算法好坏、效率高低估且不论，至少该保证它是正确的吧？下面说说代码中存在的问题。

我一看到node的定义就很纳闷，为什么要定义3个指针？于是带着这个疑问我继续往下看。

a745043791没玩过ACM，所以对于这题是多组测试数据这些环节就不追就了，主要看你的算法思想是否正确。

p1这个动态二维数组的构造方式还是不错的，不过很遗憾，到最后你也没释放任何你动态申请的内存。

当看到下一组循环时，明白了node里指针的意义，用以指向相邻的海拔低于当前结点的结点。
这里就有错了，谁告诉你最多只有3个相邻城市低于当前城市的？这里存在越界可能。

start数组，从之后的操作看，作者本意想对地图顶行城市按海拔高低作个排序。
不过，很遗憾，你得到的数组将全是海拔最高（或第一个是最高，其它是第二高）城市的列坐标。

end数组，保存的是对地图底行城市能否引水入城的标志。

xiu函数是深度优先遍历顶行某城能灌溉的所有城市。
首先，递归的深度优先用在这里就不好。
你的p1中的指针构成的不是一个树状结构，而是一个充满网格的无环有向图，深度可能非常大。
在这种结构下用深度优先遍历，而且你还不加任何消重措施，有大量结点将被重复遍历。
其结果是时间消耗将达到不可容忍的地步。
这题的最大数据量是 500 X 500 的地图，我可以负责任的告诉你，大部分这样规模的数据你的算法在你有生之年是计算不出结果的。
而题目要求的计算时间是不超过1秒。

抛开效率不说，如果这就是你在node里加个指针数组的原因，那我再次表示遗憾。这些东西华而不实，用在这里完全没有必要，一个简单的二维整型数组足矣。

之后主函数中用了一个简单的方法（假设start已被正确赋值）计算最少需要的引水点，就是从海拔最高的滨湖城市依次开始装设引水设施，直到沙漠城市都引到水。这个想法也是不对的，原因不在这里解释了。pangding的思路就是被卡在了这里。

收到的鲜花

• 有容就大 于 2012-08-19 21:10 送鲜花  10朵   附言：杨大哥 阅贴仔细 指点到位 我很赞同。

看到大神的评论时，我真的非常汗颜，不过真的要谢谢大神的批评指正，我以后一定努力。

我的代码没AC，发上来都不好意思的，大家多多批评指正。

南开的一直是system error。

搜索结果的函数应该可以再优化的，不过一时想不出什么好办法。

正确代码在55楼，错误的代码就删掉了。

[ 本帖最后由 demonleer 于 2012-8-20 10:45 编辑 ]

收到的鲜花

• 有容就大 于 2012-08-19 21:11 送鲜花  10朵   附言：哈哈 D版的代码出炉了 欣赏

呃，兄弟，我刚发现system error的原因。注意，南开的题目要求与杭电那题是不同的。只有一组数据

只有一组数据？ 我再去试试看

呵呵 直接赋值 这个有点和题意不相符呢