本文共 1670 字，大约阅读时间需要 5 分钟。
题意：在一个R*C的矩阵里，留了n个青蛙的脚印。已知每只青蛙的步长是一定的，且都是从一个边界外，跳到了另一边的边界外，而且跳的是直线，每跳一次留下一个脚印。现在求留下最多脚印的那只青蛙留下了多少脚印。也就是求哪条直线上的点最多，注意，如果少于3个点，输出0。
算法：模拟。两点确定一条直线，枚举任意的两个点，计算所确定直线上被青蛙破坏的点。
#include #include using namespace std;struct POINT{ int r; int c;};POINT points[5001];bool vis[5001][5001]; // 记录稻田是否被破坏 // 按(r,c)降序排序 bool cmp(const POINT &a, const POINT &b){ if (a.r < b.r ) { return true; } else if (a.r == b.r) { return a.c < b.c; } return false;}int main(){ int R,C,num; cin >> R >> C >> num; for (int i=0; i > points[i].r >> points[i].c; vis[points[i].r][points[i].c] = true; } /* 为什么要对点按照(行，列)降序排序呢？ 先保留疑问，假设对点已经排序过。 对点进行编号：0,1,2,3,4... 我们枚举的顺序是(0,1) (0,2) (0,3) (0,4) (1,2) (1,3) (1,4)...(i,j)... 两点确定一条直线，理论上说，对一条直线，枚举任意的两个点都可以遍历该直线上的点。 但是，算法是要讲究效率的，也就是说，我们希望对一条直线仅枚举一次。 那么，怎么确定当前要枚举的点(i,j)所确定的直线是否已经枚举过呢？ 因为我们已经排过序，可以肯定，对某条直线上的所有点，其起始点一定在最前面，因为起始点的行号一定最小。 所以枚举的时候一定会有一种情况 (起始点，下一个点) ，我们要枚举且仅枚举的只有这一个点！！！ 因此对于枚举的点(i,j)，通过计算如果i的上一个点在稻田外，说明点i是起始点，否则点i不是起始点，也就不需要继续向下执行。 例如：[4,2],[2,6],[3,4] 排序后：[2,6],[3,4],[4,2] 在枚举([3,4],[4,2])的是否，发现点[3,4]的上一个点是[2,6]，该点在稻田内，说明点[3,4]不是起始点。 感觉好啰嗦...... */ sort(points,points+num,cmp); int ans = 0; for (int i=0; i =1 && tmpx<=R && tmpy>=1 && tmpy<=C) { // 此处的[tmpx,tmpy]就是相对点i的上一个点，如果在稻田内，说明i不是起始点，不需要继续向下执行 continue; } tmpx = points[j].r - dx; tmpy = points[j].c - dy; int cnt = 2; while(tmpx>=1 && tmpx<=R && tmpy>=1 && tmpy<=C) { if (vis[tmpx][tmpy]) { cnt++; } else { cnt = 0; break; } tmpx = tmpx - dx; tmpy = tmpy - dy; } if (cnt > ans) { ans = cnt; } } } (ans < 3)? cout << 0 << endl : cout << ans << endl;}
转载地址：http://wglbb.baihongyu.com/