題目：第三題：街道問題
第三題、設有壹個N＊M（l＜＝ N＜＝50， l＜＝ M＜＝ 50）的街道（如圖壹）：（40%）
圖壹
規定行人從A(1,1)出發，在街道上只能向東或北方向行走。
圖二為N＝3，M=3的街道圖：從A出發到達B***有6條可供行走的路徑：
圖二
1. A-A1-A2-A5-B
2. A-A1-A4-A5-B
3. A-A1-A4-A7-B
4. A-A3-A4-A5-B
5. A-A3-A4-A7-B
6. A-A3-A6-A7-B
若在N＊M的街道中，設置壹個矩形障礙區域（包括圍住該區域的的街道）不讓行人通 行，如圖壹中用“＊”表示的部分。此矩形障礙區域用2對頂點坐標給出,圖壹中的2對頂點坐標為:(2，2),(8，4),此時從 A出發到達B的路徑僅有兩條。程序要求：任務壹：給出N，M後，求出所有從A出發到達B的路徑的條數。
任務二：給出N，M，同時再給出此街道中的矩形障礙區域的2對頂點坐標(X1,y1), （X2，Y2），然後求出此種情況下所有從A出發到達B的路徑的條數。
題目：第三題：騎士遊歷
第三題、騎士遊歷:設有壹個n*m的棋盤(2<=n<=50,2<=m<=50),在棋盤上任壹點有壹個中國象棋馬,馬走的規則為:
1.馬走日字，從（1，1）可以走到（2，3）和（3，2） 2.馬只能向右走
任務1:當N,M 輸入之後,找出壹條從左下角到右上角的路徑。
例如:輸入 N=4,M=4 輸出:路徑的格式:(1,1)->(2,3)->(4,4)若不存在路徑,則輸出"no"
任務2:當N,M 給出之後,同時給出馬起始的位置和終點的位置,試找出從起點到終點的所有路徑的數目。
例如:(N=10,M=10),(1,5)(起點),(3,5)(終點) 輸出:2(即由(1,5)到(3,5)***有2條路徑)
輸入格式:n,m,x1,y1,x2,y2(分別表示n,m,起點坐標,終點坐標)
輸出格式:路徑數目(若不存在從起點到終點的路徑,輸出0)
題目：第壹題：攔截導彈
第壹題：攔截導彈（28分）
某國為了防禦敵國的導彈襲擊，發展出壹種導彈攔截系統。但是這種導彈攔截系統有壹個缺陷：雖然它的第壹發炮彈能夠達到任意的高度，但是以後每壹發炮彈都不能高於前壹發炮彈的高度。某天，雷達捕捉到敵國的導彈來襲。由於該系統還在試用階段，所以只有壹套系統，因此不能保證攔截所有的導彈。
輸入導彈依次飛來的高度（雷達給出的高度數據是不大於30000的正整數），計算這套系統最多能攔截多少導彈，和如果要攔截所有導彈最少要配備多少套這種導彈攔截系統。
樣例： INPUT OUPUT
389 207 155 300 299 170 158 65 6 (最多能攔截的導彈數)
2 (要攔截所有導彈最少要配備的系統數)
題目：第三題：乘積最大
第三題：乘積最大 (26分)
問題描述:
今年是國際數學聯盟確定的“2000——世界數學年”，又恰逢我國著名數學家華羅庚先生誕辰90周年。在華羅庚先生的家鄉江蘇金壇，組織了壹場別開生面的數學智力競賽的活動，妳的壹個好朋友XZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣壹道題目:
設有壹個長度N的數字串，要求選手使用K個乘號將它分成K+1個部分，找出壹種分法，使得這K+1個部分的乘積能夠為最大。
同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的壹個例子：
有壹個數字串: 312，當N=3，K=1時會有以下兩種分法：
1）3*12=36
2）31*2=62
這時，符合題目要求的結果是： 31*2=62
現在，請妳幫助妳的好朋友XZ設計壹個程序，求得正確的答案。
輸入：
程序的輸入***有兩行:
第壹行***有2個自然數N,K (6<=N<=40，1<=K<=6)
第二行是壹個K度為N的數字串。
輸出:
結果顯示在屏幕上，相對於輸入，應輸出所求得的最大乘積（壹個自然數）。
樣例:
輸入
4 2
1231
輸出
62
題目：第四題：方格取數
第四題、方格取數 (33分)
問題描述
設有N*N的方格圖(N≤8)：我們將其中的某些方格中填入正整數，而其他的方格中則放入數字0。如下圖所示(見樣例)：
A
13 6
7
14
21 4
15
14
B
某人從圖的左上角的A點出發，可以向下行走，也可以向右走，直到到達右下角的B點。在走過的路上，他可以取走方格中的數(取走後的方格中將變為數字0)。
此人從A點到B點***走兩次，試找出2條這樣的路徑，使得取得的數之和為最大。
輸 入
輸入的第壹行為壹個整數N(表示N*N的方格圖)，接下來的每行有三個整數，前兩個表示位置，第三個數為該位置上所放的數。壹行單獨的0表示輸入結束。
輸 出
只需輸出壹個整數，表示2條路徑上取得的最大的和。
樣 例
輸入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 2l
5 6 4
6 3 15
7 2 14
0 0 0
輸出
67