NOI 4.7 搜索 1814:恼人的青蛙
题目来源：http://noi.openjudge.cn/ch0407/1814/
1814:恼人的青蛙
总时间限制: 2000ms 单个测试点时间限制: 500ms 内存限制: 65536kB
描述
在韩国，有一种小的青蛙。每到晚上，这种青蛙会跳越稻田，从而踩踏稻子。农民在早上看到被踩踏的稻子，希望找到造成最大损害的那只青蛙经过的路径。每只青蛙总是沿着一条直线跳越稻田，而且每次跳跃的距离都相同。
如下图所示，稻田里的稻子组成一个栅格，每棵稻子位于一个格点上。而青蛙总是从稻田的一侧跳进稻田，然后沿着某条直线穿越稻田，从另一侧跳出去
如下图所示，可能会有多只青蛙从稻田穿越。青蛙的每一跳都恰好踩在一棵水稻上，将这棵水稻拍倒。有些水稻可能被多只青蛙踩踏。当然，农民所见到的是图4中的情形，并看不到图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来源
1054
-----------------------------------------------------
思路
枚举+剪枝。任意两点可以确定一条路径（首端+跳跃步长），用首端和跳跃步长枚举。
枚举枚举要注意两点：
1. 首端之前一跳的点不能在稻田里
2. 路径上的点必须是青蛙踩过的点
有2个最优剪枝：
1. 对首端的x坐标，如果当前最大跳跃次数后的x坐标超限，则剪枝
2. 对首端的y坐标，如果当前最大跳跃次数后的y坐标超限，则剪枝
-----------------------------------------------------
代码
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct node {
int x,y;
bool operator< (const node &nd) const
{
if (x < nd.x)
{
return true;
}
else if (x == nd.x && y < nd.y)
{
return true;
}
return false;
}
};
const int NMAX = 5005;
int r,c;
bool mat[NMAX][NMAX] = {}; // 稻田里的这棵水稻是否被踩过
node ND[5005] = {};
int cal(int x0, int y0, int dx, int dy) // 通过起点和间隔计算路径长度
{
int x = x0, y = y0, ans = 0;
while (x < r && y < c && x >= 0 && y >= 0)
{
if (mat[x][y]) // 如果这个点有效，则计数
{
ans ++;
x += dx;
y += dy;
}
else // 如果这个点无效，说明路径没有充满稻田，不是一条路径
{
return 0;
}
}
return ans;
}
int main()
{
#ifndef ONLINE_JUDGE
ifstream fin ("0407_1814.txt");
int n,i,j,x,y,x0,y0,dx,dy,ans=2;
node nd;
fin >> r >> c >> n;
for (i=0; i<n; i++)
{
fin >> x >> y;
nd.x = --x;
nd.y = --y;
mat[nd.x][nd.y] = 1;
ND[i] = nd;
}
fin.close();
sort(ND, ND+n);
for (i=0; i<n-1; i++)
{
for (j=i+1; j<n; j++)
{
x0 = ND[i].x;
y0 = ND[i].y;
dx = ND[j].x - ND[i].x;
dy = ND[j].y - ND[i].y;
if (x0 + (ans-1) * dx < 0 || x0 + (ans-1) * dx >= r) // 若长度为ans时x方向已经越界，剪枝
{
break;
}
if (y0 + (ans-1) * dy < 0 || y0 + (ans-1) * dy >= c) // 若长度为ans时y方向已经越界，剪枝
{
continue;
}
if (x0-dx >= 0 && y0-dy >= 0 && x0-dx < r && y0-dy < c)// 不符合条件（整条路径应该贯穿稻田）
{
continue;
}
ans = max(cal(x0,y0,dx,dy),ans); // 维护最大长度
}
}
cout << ((ans>2)? ans:0); // 舍弃长度小于等于2的路径
return 0;
#endif
#ifdef ONLINE_JUDGE
int n,i,j,x,y,x0,y0,dx,dy,ans=2;
node nd;
cin >> r >> c >> n;
for (i=0; i<n; i++)
{
cin >> x >> y;
nd.x = --x;
nd.y = --y;
mat[nd.x][nd.y] = 1;
ND[i] = nd;
}
sort(ND, ND+n);
for (i=0; i<n-1; i++)
{
for (j=i+1; j<n; j++)
{
x0 = ND[i].x;
y0 = ND[i].y;
dx = ND[j].x - ND[i].x;
dy = ND[j].y - ND[i].y;
if (x0 + (ans-1) * dx < 0 || x0 + (ans-1) * dx >= r) // 若长度为ans时x方向已经越界，剪枝
{
break;
}
if (y0 + (ans-1) * dy < 0 || y0 + (ans-1) * dy >= c) // 若长度为ans时y方向已经越界，剪枝
{
continue;
}
if (x0-dx >= 0 && y0-dy >= 0 && x0-dx < r && y0-dy < c)// 不符合条件（整条路径应该贯穿稻田）
{
continue;
}
ans = max(cal(x0,y0,dx,dy),ans); // 维护最大长度
}
}
cout << ((ans>2)? ans:0); // 舍弃长度小于等于2的路径
return 0;
#endif
}