问题描述

2017-10-01 21-05-50 创建的截图.png

2017-10-01 21-05-53 创建的截图.png

2017-10-01 21-05-59 创建的截图.png

2017-10-01 21-06-06 创建的截图.png

题目要求

2017-10-01 21-06-13 创建的截图.png

程序输入

2017-10-01 21-07-01 创建的截图.png

程序输出

2017-10-01 21-07-07 创建的截图.png

样例

2017-10-01 21-07-10 创建的截图.png

解题思路

2017-10-01 21-09-53 创建的截图.png

2017-10-01 21-10-44 创建的截图.png

2017-10-01 21-10-54 创建的截图.png

2017-10-01 21-11-18 创建的截图.png

注意

2017-10-01 21-11-29 创建的截图.png

2017-10-01 21-17-06 创建的截图.png

2017-10-01 21-13-58 创建的截图.png

程序实现

#include<iostream>
#include<algorithm>

using namespace std;

int R,C,N;//行数,列数,被踩水稻数

struct Plant{
int x;
int y;
Plant(){}
Plant(int m,int n){x=m;y=n;}
};

bool operator < (const Plant& p1,const Plant& p2){
if(p1.x==p2.x) return p1.y<p1.y;
return p1.x<p2.x;
}

int main(){
cin>>R>>C;//输入行数和列数,x方向是上下,y方向是左右
cin>>N;
int i,j,dX,dY,pX,pY,maxs=2,steps;
Plant plant[N];
for(i=0;i<N;i++)
    cin>>plant[i].x>>plant[i].y;
sort(plant,plant+N);//将plant按x坐标从小到大排序,x坐标相同的按y坐标从小到大排序
for(i=0;i<N-2;i++)//plant[i]是第一个点
    for(j=i+1;j<N-1;j++)//plant[j]是第二个点
        {
        dX=plant[j].x-plant[i].x;
        dY=plant[j].y-plant[i].y;
        pX=plant[i].x-dX;
        pY=plant[i].y-dY;
        if(pX<=R and pX>=1 and pY<=C and pY>=1)
            continue;//第一点的前一点在田里,说明第二点选择不合理,导致步长太小
        if(plant[i].x+(maxs-1)*dX>R)
            break;//最小步长下,x方向过早越界,说明第一点不合理
        if(plant[i].y+(maxs-1)*dY>C or plant[i].y+(maxs-1)*dY<1)
            continue;//y方向过早越界,第二点选择不合理

        steps=3;
        while(pX+dX*steps<=R and pX+dX*steps>=1 and pY+dY*steps<=C and pY+dY*steps>=1){
        //看看从这两点出发一共能走多少步
        Plant tmpPlant(pX+dX*steps,pY+dY*steps);
        if(binary_search(plant+j+1,plant+N,tmpPlant)) steps++;
        else {//每一步都必须在田里,否则就不是一条合理路径
        steps=0;break;}
        }
        if(maxs<steps-1) maxs=steps-1;
        }

if(maxs==2) cout<<0<<endl;
else cout<<maxs<<endl;
return 0;
}