题目

1814:恼人的青蛙
查看提交统计提问
总时间限制: 2000ms 单个测试点时间限制: 500ms 内存限制: 65536kB
描述
在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同。

如下图所示，稻田里的稻子组成一个栅格，每棵稻子位于一个格点上。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去

如下图所示，可能会有多只青蛙从稻田穿越。青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。有些水稻可能被多只青蛙踩踏。当然，农民所见到的是图4中的情形，并看不到图3中的直线，也见不到别人家田里被踩踏的水稻。

根据图4，农民能够构造出青蛙穿越稻田时的行走路径，并且只关心那些在穿越稻田时至少踩踏了3棵水稻的青蛙。因此，每条青蛙行走路径上至少包括3棵被踩踏的水稻。而在一条青蛙行走路径的直线上，也可能会有些被踩踏的水稻不属于该行走路径 ①不是一条行走路径：只有两棵被踩踏的水稻； ②是一条行走路径，但不包括（2，6）上的水道； ③不是一条行走路径：虽然有3棵被踩踏的水稻，但这三棵水稻之间的距离间隔不相等。 请你写一个程序，确定：在一条青蛙行走路径中，最多有多少颗水稻被踩踏。例如，图4的答案是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

分析

0.任意方向都可以
1.少于三个点不是
2.一条路线上可以有多的点
3.间隔要一致
4.没有输出0
5.最多5000行列5000稻草，遍历一个点出发的n个斜线，那共nnn条线，就是7510^9
6.共5000个稻草，每个遍历5000个稻草，需要2510^6好一点

每个点有行列
所有的点从左往右从上往下排序。
每两个点，计算行差dx=x2-x1和列差dy=y2-y1，然后往下计算x2+=dx，y2+=dy
判断界内x>=1&&x<=r&&y>=1&&y<=c，有稻草k[x][y]==true
如果往前x1-dx,y1-dy,还有点就剪枝
往后一直到越界，算式一种方案。如果中间没有点了，那就不是方案

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5010;
struct point{
	int x,y;//行列 
	bool operator<(const point& p)const{//const定义常量，在函数内部不可以修改 p 的值
	//&表示p是一个引用。引用是对象的别名，它和对象本身指向同一块内存地址。 
	//函数const不可以修改this，并且允许常量对象调用operator<函数。
	//sort排序函数默认使用 < 运算符来确定元素的顺序。 
		if(x!=p.x)return x<p.x;//升序 
		else return y<p.y;
	}
}v[N];//所有稻草点。
int r,c,n,maxd=0;
int k[N][N];//标识
void view(){
	cout<<"向量\n";
	for(int i=0;i<n;i++)cout<<v[i].x<<" ";cout<<endl;
	for(int i=0;i<n;i++)cout<<v[i].y<<" ";cout<<endl;
}
void view(int s,int t,int d[][N],int maxd){
	cout<<endl<<s<<"到"<<t<<"\t最大"<<maxd<<endl;
	for(int i=1;i<=r;i++){
		for(int j=1;j<=c;j++)cout<<k[i][j]<<"\t";cout<<endl;
	}
}
bool judge(int x,int y){
	return x>=1&&x<=r&&y>=1&&y<=c;
}
int main(){
	//freopen("data.cpp","r",stdin);
	cin>>r>>c>>n;
	for(int i=0;i<n;i++){
		cin>>v[i].x>>v[i].y;
		k[v[i].x][v[i].y]=-1;
	}
	//view();
	sort(v,v+n);
	//view();
	//view(0,n,k,0);
	int id=1;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			int dx=v[j].x-v[i].x,dy=v[j].y-v[i].y;//两稻草间间距 
			if(judge(v[i].x-dx,v[i].y-dy))continue;//确定i稻草是该线路的第一个（剪枝） 
			k[v[i].x][v[i].y]=k[v[j].x][v[j].y]=id;
			int hh=1,tx=v[j].x,ty=v[j].y;
			while(judge(tx,ty)){//没越界 
				if(k[tx][ty]){//有稻草 
					hh++;k[tx][ty]=id;
				}else{hh=0;break;}//没稻草，不成立 
				tx+=dx,ty+=dy;//同样间隔后的点 
			}
			if(hh>2&&hh>maxd){
				maxd=hh;
				//view(i,j,k,maxd);
				//id++;
			}
		}
	}
	cout<<maxd<<endl;
	return 0;
}

分析

小结

• 两点一条线，往前还有点就剪枝
• 两点一条线，往后等差找到新点，一直到界外就是一种方案，否则不是
• 要排序
• 挺简单的，但是还是要有勇气落实想法。