0031-讨厌的青蛙

问题描述

在韩国,有一种小的青蛙。每到晚上,这种青蛙会跳越稻田,从而踩踏稻子。农民在早上看到被踩踏的稻子,希望找到造成最大损害的那只青蛙经过的路径。 每只青蛙总是沿着一条直线跳越稻田,而且每次跳跃的距离都相同,如图 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 行中,每行有两个整数,分别是一颗被踩踏水稻的行号(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

算法实现

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;
                    }
                }
            }
        }
    }
}