问题描述
在韩国,有一种小的青蛙。每到晚上,这种青蛙会跳越稻田,从而踩踏稻子。农民在早上看到被踩踏的稻子,希望找到造成最大损害的那只青蛙经过的路径。 每只青蛙总是沿着一条直线跳越稻田,而且每次跳跃的距离都相同,如图 1所示。 稻田里的稻子组成一个栅格,每棵稻子位于一个格点上,如图2 所示。而青蛙总是从稻田的一侧跳进稻田,然后沿着某条直线穿越稻田,从另一侧跳出去,如图 3 所示。 青蛙的每一跳都恰好踩在一棵水稻上, 将这棵水稻拍倒。可能会有多只青蛙从稻田穿越,有些水稻被多只青蛙踩踏,如图4 所示。当然,农民所见到的是图 5 中的情形,看不到图 4 中的直线。 根据图 5,农民能够构造出青蛙穿越稻田时的行走路径,并且只关心那些在穿越稻田时至少踩踏了 3 棵水稻的青蛙。因此,每条青蛙行走路径上至少包括 3 棵被踩踏的水稻。而在一条青蛙行走路径的直线上,也可能会有些被踩踏的水稻不属于该行走路径。 在图 5 中,格点(2, 1)、(6, 1)上的水稻可能是同一只青蛙踩踏的,但这条线上只有两棵被踩踏的水稻,因此不能作为一条青蛙行走路径;格点(2, 3)、(3, 4)、(6, 6)在同一条直线上,但它们的间距不等,因此不能作为一条青蛙行走路径;格点(2, 1)、(2, 3)、(2, 5)、(2, 7)是一条青蛙行走路径,该路径不包括格点(2, 6)。请你写一个程序,确定在所有的青蛙行路径中,踩踏水稻棵数最多的路径上有多少棵水稻被踩踏。例如,图5 的答案是 7,因为第 6 行上全部水稻恰好构成一条青蛙行走路径。
输入
从标准输入设备上读入数据。第一行上两个整数 R、C,分别表示稻田中水稻的行数和列数,1≤R、C≤5000。第二行是一个整数 N,表示被踩踏的水稻数量, ≤N≤5000。在剩下的 N 行中,每行有两个整数,分别是一颗被踩踏水稻的行号(1R)和列号(1C),两个整数用一个空格隔开。而且,每棵被踩踏水稻只被列出一次。
输出
从标准输出设备上输出一个整数。如果在稻田中存在青蛙行走路径,则输出包含最多水稻的青蛙行走路径中的水稻数量,否则输出 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
算法实现
using System;
namespace Questions{
class Program{
public static void Main(string[] args){
string input = Console.ReadLine();
string[] data = input.Split(' ');
int r = int.Parse(data[0]);
int c = int.Parse(data[1]);
int n = int.Parse(Console.ReadLine());
int[,] num = new int[n, 2];
for (int i = 0; i < n; i++)
{
input = Console.ReadLine();
data = input.Split(' ');
num[i, 0] = int.Parse(data[0]);
num[i, 1] = int.Parse(data[1]);
}
Sort(ref num);
int max = 0;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int temp = 0;
int dx = num[j, 0] - num[i, 0];
int dy = num[j, 1] - num[i, 1];
temp++;
int x = num[i, 0];
int y = num[i, 1];
while (true)
{
if (x - dx > 0 && y - dy > 0 && x - dx <= r && y - dy <= c)
{
temp++;
x -= dx;
y -= dy;
}
else
break;
}
temp++;
x = num[j, 0];
y = num[j, 1];
while (true)
{
if (x + dx <= r && y + dy <= c && x + dx > 0 && y + dy > 0)
{
temp++;
x += dx;
y += dy;
}
else
break;
}
max = max > temp ? max : temp;
}
}
Console.WriteLine(max);
Console.ReadKey();
}
public static void Sort(ref int[,] sort)
{
for (int i = 0; i < sort.GetLength(0) - 1; i++)
{
for (int j = 0; j < sort.GetLength(0) - 1 - i; j++)
{
if (sort[j, 0] > sort[j + 1, 0] || (sort[j, 0] == sort[j + 1, 0] && sort[j, 1] > sort[j + 1, 1]))
{
int temp = sort[j, 0];
sort[j, 0] = sort[j + 1, 0];
sort[j + 1, 0] = temp;
temp = sort[j, 1];
sort[j, 1] = sort[j + 1, 1];
sort[j + 1, 1] = temp;
}
}
}
}
}
}