資源描述：
《《ACM算法與程序設(shè)計(jì)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、電子科技大學(xué)期末解題報(bào)告課程：《ACM算法與程序設(shè)計(jì)》學(xué)院：學(xué)號：姓名：報(bào)告成績：教師簽名：討厭的青蛙1、鏈接地址http://poj.grids.cn/problem?id=28122、問題描述在韓國，有一種小的青蛙。每到晚上，這種青蛙會(huì)跳越稻田，從而踩踏稻子。農(nóng)民在早上看到被踩踏的稻子，希望找到造成最大損害的那只青蛙經(jīng)過的路徑。每只青蛙總是沿著一條直線跳越稻田，而且每次跳躍的距離都相同，如圖1所示。稻田里的稻子組成一個(gè)柵格，每棵稻子位于一個(gè)格點(diǎn)上，如圖2所示。而青蛙總是從稻田的一側(cè)跳進(jìn)稻田，然后沿著某條直線穿越稻田，從另一側(cè)跳出去，如圖3所示。問題描述青蛙的每一跳都恰好踩在一棵水稻上，
2、將這棵水稻拍倒?？赡軙?huì)有多只青蛙從稻田穿越，有些水稻被多只青蛙踩踏，如圖4所示。當(dāng)然，農(nóng)民所見到的是圖5中的情形，看不到圖4中的直線。根據(jù)圖5，農(nóng)民能夠構(gòu)造出青蛙穿越稻田時(shí)的行走路徑，并且只關(guān)心那些在穿越稻田時(shí)至少踩踏了3棵水稻的青蛙。因此，每條青蛙行走路徑上至少包括3棵被踩踏的水稻。而在一條青蛙行走路徑的直線上，也可能會(huì)有些被踩踏的水稻不屬于該行走路徑。在圖5中，格點(diǎn)(2,1)、(6,1)上的水稻可能是同一只青蛙踩踏的，但這條線上只有兩棵被踩踏的水稻，因此不能作為一條青蛙行走路徑；格點(diǎn)(2,3)、(3,4)、(6,6)在同一條直線上，但它們的間距不等，因此不能作為一條青蛙行走路徑；格點(diǎn)(
3、2,1)、(2,3)、(2,5)、(2,7)是一條青蛙行走路徑，該路徑不包括格點(diǎn)(2,6)。請你寫一個(gè)程序，確定在所有的青蛙行路徑中，踩踏水稻棵數(shù)最多的路徑上有多少棵水稻被踩踏。例如，圖5的答案是7，因?yàn)榈?行上全部水稻恰好構(gòu)成一條青蛙行走路徑。輸入數(shù)據(jù)從標(biāo)準(zhǔn)輸入設(shè)備上讀入數(shù)據(jù)。第一行上兩個(gè)整數(shù)R、C，分別表示稻田中水稻的行數(shù)和列數(shù)，1≤R、C≤5000。第二行是一個(gè)整數(shù)N，表示被踩踏的水稻數(shù)量，3≤N≤5000。在剩下的N行中，每行有兩個(gè)整數(shù)，分別是一顆被踩踏水稻的行號(1~R)和列號(1~C)，兩個(gè)整數(shù)用一個(gè)空格隔開。而且，每棵被踩踏水稻只被列出一次。輸出要求從標(biāo)準(zhǔn)輸出設(shè)備上輸出一個(gè)整
4、數(shù)。如果在稻田中存在青蛙行走路徑，則輸出包含最多水稻的青蛙行走路徑中的水稻數(shù)量，否則輸出0。輸入樣例67142166422526273461622363646567輸出樣例73、解題思路這個(gè)問題看起來很復(fù)雜，其實(shí)目的很簡單：幫助農(nóng)民找到為害最大的青蛙。也就是要找到一條穿越稻田的青蛙路徑，這個(gè)路徑上被踩踏的水稻不少于其他任何青蛙路徑上被踩踏的水稻數(shù)。當(dāng)然，整個(gè)稻田中也可能根本就不存在青蛙路徑。問題的關(guān)鍵是：找到穿越稻田的全部青蛙路徑。任何一條穿越稻田的青蛙路徑L，至少包括3棵被踩踏的水稻。假設(shè)其中前兩棵被踩踏的水稻分別是(X1，Y1)、(X2，Y2)，那么：l令dx=X2-X1、dy=Y2-
5、Y1；X0=X1-dx、Y0=Y1-dy；X3=X2+dx、Y3=Y2+dyl(X0,Y0)位于稻田之外，青蛙從該位置經(jīng)一跳后進(jìn)入稻田、踩踏位置(X1,Y1)上的水稻lXi=X0+i×dx、Yi=Y1+i×dy(i>3)，如果(Xi,Yi)位于稻田之內(nèi)，則(Xi,Yi)上的水稻必被青蛙踩踏根據(jù)上述規(guī)則，只要知道一條青蛙路徑上的前兩棵被踩踏的水稻，就可以找到該路徑上其他的水稻。為了找到全部的青蛙路徑，只要從被踩踏的水稻中，任取兩棵水稻(X1,Y1)、(X2,Y2)，判斷(X1,Y1)、(X2,Y2)是否能夠作為一條青蛙路徑上最先被踩踏的兩顆水稻。4、解決方案這個(gè)問題的描述中，最基本的元素是被
6、踩踏的水稻。在程序中要選擇一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)，來表達(dá)這個(gè)基本元素。這個(gè)數(shù)據(jù)結(jié)構(gòu)是否合適的標(biāo)準(zhǔn)是：在程序中要表達(dá)這個(gè)元素時(shí)，能否用一個(gè)單詞或者短語，即用一個(gè)變量來表示。structPLANT//描述一棵被踩踏的水稻{intx;//水稻的行號inty;//水稻的列號}這個(gè)問題的主要計(jì)算是：從被踩踏的水稻中選擇兩棵(X1,Y1)、(X2,Y2)。判斷它們是否能夠作為一條青蛙路徑上最先被踩踏的兩顆水稻。(X1,Y1)、(X2,Y2)唯一確定了蛙跳的方向和步長，從(X2,Y2)開始，沿著這個(gè)方向和步長在稻田內(nèi)走。每走一步，判斷所到達(dá)位置上(X,Y)的水稻是否被踩踏，直到走出稻田為止。如果在某一步上，
7、(X,Y)沒有被踩踏，則表明(X1,Y1)、(X2,Y2)是一條青蛙路徑上最先被踩踏的兩顆水稻的假設(shè)不成立。這個(gè)判斷的算法在問題求解過程中要反復(fù)使用，它的效率成為決定整個(gè)計(jì)算效率的關(guān)鍵。l用一個(gè)PLANT型的數(shù)組plants[5001]表示全部被踩踏的水稻l將plants中的元素按照行/列序號的升序(或者降序)排列l(wèi)采用二分法查找plants中是否有值為(X,Y)的元素：將(X,Y)與plants中間的元素比較，(1)相
