问题描述

在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早

上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一

条直线跳越稻田，而且每次跳跃的距离都相同，如图8-4 所示。 稻田里的稻子组成一个栅

格，每棵稻子位于一个格点上，如图8-5 所示。而青蛙总是从稻田的一侧跳进稻田，然后沿

着某条直线穿越稻田，从另一侧跳出去，如图8-6 所示。

青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。可能会有多只青蛙从稻田穿越，

有些水稻被多只青蛙踩踏，如图8-7 所示。当然，农民所见到的是图8-8 中的情形，看不到

图8-7中的直线。

根据图8-8，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田

时至少踩踏了3 棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3 棵被踩踏的水稻。而

在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径。在图8-8 中，

格点(2, 1)、(6, 1)上的水稻可能是同一只青蛙踩踏的，但这条线上只有两棵被踩踏的水稻，

因此不能作为一条青蛙行走路径；格点(2, 3)、(3, 4)、(6, 6)在同一条直线上，但它们的间距

不等，因此不能作为一条青蛙行走路径；格点(2, 1)、(2, 3)、(2, 5)、(2, 7)是一条青蛙行走路

径，该路径不包括格点(2, 6)。请你写一个程序，确定在所有的青蛙行路径中，踩踏水稻棵

数最多的路径上有多少棵水稻被踩踏。例如，图8-8 的答案是7，因为第6 行上全部水稻恰

好构成一条青蛙行走路径。

输入数据

从标准输入设备上读入数据。第一行上两个整数R、C，分别表示稻田中水稻的行数和

列数，1≤R、C≤5000。第二行是一个整数N，表示被踩踏的水稻数量， 3≤N≤5000。在剩下

的N 行中，每行有两个整数，分别是一颗被踩踏水稻的行号(1~R)和列号(1~C)，两个整数用

一个空格隔开。而且，每棵被踩踏水稻只被列出一次。

输出要求

从标准输出设备上输出一个整数。如果在稻田中存在青蛙行走路径，则输出包含最多水

稻的青蛙行走路径中的水稻数量，否则输出0。

输入样例

6 7

14

2 1

6 6

4 2

2 5

2 6

2 7

3 4

6 1

6 2

2 3

6 3

6 4

6 5

6 7

输出样例

7

我的解题思路：

　　递归搜索！哈哈，最进什么问题只要能和搜索沾上边的，我总会想着用递归去解，也好，因为其它办法我还不熟练，等学习了其它办法了再去用其它的办法吧。

　　根据条件，必须在田里跳三跳以上的路径才算路径。我们就可以求出他们的每一跳的区间必须小于等于总行（列）数除以三。然后以这个区间内的数去跳，使用递归去搜索每种情况，以为它们总是沿着直线跳，那么递归里面的改变值是固定的，所以程序里面要把Jump的i，j固定。这样才能搜索出是直线的。对于搜索，我是对每个可能的点发散它的四周去搜索，那么这样会出现很多重复的情况。不过似乎我的程序还是有点问题。因为它只从边上跑进去，那么必须是进去又出来了。那么我没考虑周全。。。我再去看看别人给出的答案吧。

#include 
     
      #define MAX 5001int nMax;int nArr[MAX][MAX];int nRow,nCol,nCount,nTimes;void output(){    int i,j;    for (i=1; i<=nRow; i++)    {        for (j=1; j<=nCol; j++)        {            printf("%d ",nArr[i][j]);        }        printf("\n");    }}void Jump(int row,int col,int i,int j){    if (((row<1) | (row>nRow) | (col<1) | (col>nCol)) && nTimes >=3)  //找到一条线路    {        nMax = nMax>nTimes?nMax:nTimes;        return;    }    else    {        if (nArr[row][col])        {            nTimes++;            Jump(row+i,col+j,i,j);        }        return;    }}int main(){    int r,c,i,j;    int nRowZone,nColZone;    FILE *fp;    fp=fopen("in.txt","r");        nMax = 0;      fscanf(fp,"%d%d",&nRow,&nCol);    printf("ROW:%d COL:%d\n",nRow,nCol);    for (r=1; r<=nRow; r++)    {        for (c=1; c<=nCol; c++)        {            nArr[r][c]=0;        }    }    fscanf(fp,"%d",&nCount);    while (nCount)    {        nCount--;        fscanf(fp,"%d%d",&r,&c);        nArr[r][c] = 1;    }    output();    nRowZone = nRow/3;    nColZone = nCol/3;    for (r=1; r<=nRow; r++)    {        for (c=1; c
     

 

题后感：

　　看过别人的方法后，我发现了自己的问题。首先，只用一个二维数组来做的话，太大，而且不好做搜索，其实比较好的方法是构造一个数据结构来存储。其次，一开始就没有想到可以寻找任意两个节点，然后计算出步长，再去判断能否构成一个路径，这才是对这道题正确并高效的解题方法。在比较任意两个节点的时候，我们还可以先对节点按行先进行排列，这样就可以做到任意一个点与它后面的每个点来比较，这样可以避免重复。

 

  这题我觉得主要还是要会判断条件方面，要考虑周全，不然就会TLE。还有就是要判断不存在的情况。同时学会运用qsort和bsearch函数。

#include 
     
      #include 
      
       typedef struct PLANT{    int r,c;}PLANTS;PLANTS plants[5001];int row,col,n;int myCmp(const void *p1, const void *p2){    PLANTS *plantA,*plantB;    plantA = (PLANTS *)p1;    plantB = (PLANTS *)p2;    if (plantA->r == plantB->r) return(plantA->c - plantB->c);    return (plantA->r - plantB->r);}int SearchPath(PLANTS p, int x, int y){    int steps;    PLANTS plant = p;    plant.r = p.r + x;    plant.c = p.c + y;    steps=2;    while ((plant.r <= row) && (plant.r >= 1) && (plant.c >= 1) && (plant.c <= col))    {        if (!bsearch(&plant,plants,n,sizeof(PLANTS),myCmp))          {            steps=0;   //不能构成路径            break;        }        steps++;        plant.r = plant.r + x;        plant.c = plant.c + y;    }    return steps;}int main(){    int i,j,max=2;    int dX,dY,pX,pY;    //FILE *fp;    int steps;    //fp=fopen("in.txt","r");    scanf("%d%d",&row,&col);    scanf("%d",&n);    for (i=0; i
       
        = 1 && pX <= row && pY >= 1 && pY <= col)            {                continue;            }                        //下面这两个if条件是判断下一步是不是在稻田里，不在的话就不用考虑了                if ((plants[i].c + max*dY < 1) || (plants[i].c + max*dY > col))            {                continue;            }            if (plants[i].r + max*dX > row)            {                break;            }                        steps = SearchPath(plants[j],dX,dY);            max = max>steps?max:steps;                }    }    if (max == 2) max=0;    printf("%d\n",max);    return 0;} 2013/4/30 19:29