d198: 00825 - Walking on the Safe Side
標籤 : DP 排列組合
通過比率 : 183人/281人 ( 65% ) [非即時]
評分方式:
Tolerant

最近更新 : 2012-11-28 17:52

內容

在正方城這個城市走路是件相當容易的事,因為所有的道路都是像棋盤的線一樣,把城市切割成一塊一塊的正方形。大部分的十字路口都是安全的,行人可以直接通過。然而也有少數的十字路口比較危險,所以建有地下道或天橋供行人通過。

現 在有一個人想要從位於城市西北方(也就是左上角)的公園十字路口到位於東南方(也就是右下角)的車站十字路口去。由於他是個懶惰的人,他不想要走比需要多 一點點的路,也就是說他一定是往下或往右走,絕對不會往上或往左走。另外,他也不喜歡走天橋或地下道,所以他會避開這些危險的十字路口。你的任務就是幫他 算一下從左上角走到右下角有多少種不同的走法。

以下的圖顯示出有4條東西向的道路,有5條南北向的道路,有3個十字路口是危險的。所以從左上角走到右下角要走(N-1)+(W-1) = 3+4 = 7格的距離,並且總共有4種不同的走法。

輸入說明
輸入的第一列有一個正整數,代表以下有多少組測試資料。每組測試資料的第一列有2個整數W,N(均不大於100),W代表東西向道路的數目,N代表南北向 道路的數目,編號如上圖所示。接下來的W列代表這W條東西向道路,每列的第一個數為這是第幾條東西向道路,接下來有0個或多個不等的數,代表某些南北向道 路與這條東西向道路相交的十字路口是危險的。

輸入的第一列與第一組測試資料之間,以及各組測試資料之間均有一空白列,第一組Sample Input表示的路如上圖所示,請參考。

輸出說明
每組測試資料輸出一列,為一個整數。代表這個人從左上角走到右下角有多少種不同的走法。

測試資料間亦請空一列。

範例輸入
2

4 5
1
2 2
3 3 5
4

5 5
1
2 1 2 3 4 
3 1 2 3  
4 1 2 3 5  
5 1 2 3 
範例輸出
4

0
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :
標籤:
DP 排列組合
出處:
UVa825 [管理者:
taichunmin (和風信使)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」