Strict Standards: call_user_func_array() expects parameter 1 to be a valid callback, non-static method HTML_content::show() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/Cache/Lite/Function.php on line 98

Strict Standards: Non-static method HTML_content::_Itemid() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 452

Strict Standards: Non-static method HTML_content::_linkInfo() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 455

Strict Standards: Non-static method HTML_content::Title() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 470

Strict Standards: Non-static method HTML_content::PdfIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 473

Strict Standards: Non-static method mosHTML::PrintIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 476

Strict Standards: Non-static method mosAdminMenus::ImageCheck() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/includes/joomla.php on line 2329

Strict Standards: Non-static method HTML_content::EmailIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 479
Frogs - Con ếch
Strict Standards: Non-static method HTML_content::EditIcon() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 632

Strict Standards: Non-static method HTML_content::Section_Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 511

Strict Standards: Non-static method HTML_content::Section() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 755

Strict Standards: Non-static method HTML_content::Category() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 758

Strict Standards: Non-static method HTML_content::Author() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 514

Strict Standards: Non-static method HTML_content::CreateDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 517

Strict Standards: Non-static method HTML_content::URL() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 520

Strict Standards: Non-static method HTML_content::ModifiedDate() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 536

Strict Standards: Non-static method HTML_content::ReadMore() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 539
Người viết: Ngô Minh Đức   
21/04/2008

Strict Standards: Non-static method HTML_content::TOC() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 526

Con ếch

Ở Hàn Quốc, có truyền thuyết về tác hại của cheonggaeguri, Một loài ếch nhỏ. Đó là một điều đáng chú ý vì các con ếch nhảy qua ruộng lúa của bạn vào ban đêm và làm đổ gục các cây lúa. Buổi sáng sau khi ghi nhận những cây lúa bị đổ, bạn muốn biết đường đi của con ếch gây nên thảm hoạ lớn nhất. Một con ếch luôn nhảy qua ruộng lúa theo đường thẳng và mọi bước nhảy có cùng độ dài. Các con ếch khác nhau có thể nhảy với các bước có độ dài khác nhau và theo các hướng khác nhau (xem hình sau)

Ruộng lúa của bạn có các cây lúa ở trên các giao điểm của một lưới ô vuông như trong Hình 1 và các con ếch nhảy qua ruộng lúa bắt đầu từ bên ngoài ở một phía và kết thúc ở bên ngoài phía khác nhau trong Hình 2.

Có thể có nhiều con ếch nhảy qua ruộng lúa bằng cách nhay từ cây lúa này đến cây lúa khác. Mỗi bước nhảy đến một cây lúa và làm đổ gục cây lúa đó nhau trong Hình 3. Chú ý rằng một số cây có thể bị hơn một con ếch nhảy đến trong ban đêm. Tất nhiên, sáng ra bạn không thể nhìn thấy các đường đi của các con ếch và cũng không nhìn thấy được các vết nhảy của các con ếch bên ngoài ruộng lúa; với tình huống trong Hình 3, những gì bạn nhìn thấy được chỉ ra trong Hình 4:

Từ hình 4, ta có thể khôi phục mọi đường đi có thể có mà các con ếch đã nhảy qua ruộng lúa. Bạn chỉ quan tâm đến các con ếch làm đổ gục ít nhất ba cây lúa trong ruộng. Một đường đi của con ếch như vậy được gọi là một đường ếch. Chẳng hạn ba đường đi trong Hình 3 là các đường ếch (cũng có thể còn có các đường ếch khác). Đường thẳng đứng ở cột 1 có thể là một đường đi với bước nhảy độ dài 4 nhưng do chỉ có 2 cây lúa bị đổ nên không là đường ếch. Đường đi chéo gồm các cây lúa trên dòng 2 cột 3, dòng 3 cột 4 và dòng 6 cột 7 có ba cây lúa bị dổ nhưng các bước nhảy không cùng độ dài nên cũng không là một đường ếch. Ta cũng cần chú ý rằng trên đường thẳng chứa một đường ếch có thể có các cây lúa đổ khác nhưng không do con ếch đó gây nên (cây ở dòng 2, cột 6 trên đường nằm ngang đi qua dòng 2 trong Hình 4) và ngoài ra có một số cây đổ có thể không thuộc đường ếch nào.

Nhiệm vụ của bạn là viết một chương trình xác định số lượng nhiều nhất các cây lúa đổ trên một đường ếch (cực đại lấy theo mọi đường ếch có thể có). Trong Hình 4 đáp số là 7 nhận được từ đường ếch qua dòng 6.

INPUT

Chương trình của bạn cần đọc từ input chuẩn. Dòng thứ nhất gồm hai số nguyên R và C, tương ứng là số dòng và số cột trong ruộng lúa của bạn, 1 < R,C > 5000. Dòng thứ hai gồm duy nhất số nguyên N, là số cây lúa bị đổ, 3 < N > 5000. Mỗi một trong Ndòng còn lại chứa hai số nguyên tương ứng là chỉ số dòng và chỉ số cột của một cây lúa bị đổ (1 < chi? so^' do`ng < R), (1 < chỉ số cột < C) hai số này cách nhau một dấu trống. Mỗi cây lúa đổ chỉ liệt kê ra một lần.

OUTPUT

Chương trình của bạn cần viết ra output chuẩn. Output gồm một dòng với một số nguyên duy nhất, đó là số cây lúa đổ của một đường ếch gây thiệt hại lớn nhất nếu có ít nhất một đường ếch, nếu không có đường ếch nào, là số 0.

Ví dụ về input và output

Example 1: input output

(Ví dụ theo Hình 4)

Example 2: input (Ví dụ theo Hình 5)

output

Việc cho điểm

Nếu chương trình của bạn cho đáp số đúng với một test trong giới hạn thời gian thì bạn được toàn bộ điểm của test đó, nếu không, bạn được 0 điểm
 
Strict Standards: Non-static method HTML_content::Navigation() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 550

Strict Standards: Non-static method mosHTML::CloseButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 553

Strict Standards: Non-static method mosHTML::BackButton() should not be called statically in /home/vmapps4u/public_html/vnoi_v0/components/com_content/content.html.php on line 556