d198.
00825 - Walking on the Safe Side
內容
在正方城這個城市走路是件相當容易的事，因為所有的道路都是像棋盤的線一樣，把城市切割成一塊一塊的正方形。大部分的十字路口都是安全的，行人可以直接通過。然而也有少數的十字路口比較危險，所以建有地下道或天橋供行人通過。
現 在有一個人想要從位於城市西北方（也就是左上角）的公園十字路口到位於東南方（也就是右下角）的車站十字路口去。由於他是個懶惰的人，他不想要走比需要多 一點點的路，也就是說他一定是往下或往右走，絕對不會往上或往左走。另外，他也不喜歡走天橋或地下道，所以他會避開這些危險的十字路口。你的任務就是幫他 算一下從左上角走到右下角有多少種不同的走法。
以下的圖顯示出有4條東西向的道路，有5條南北向的道路，有3個十字路口是危險的。所以從左上角走到右下角要走(N-1)+(W-1) = 3+4 = 7格的距離，並且總共有4種不同的走法。
輸入說明
輸入的第一列有一個正整數，代表以下有多少組測試資料。每組測試資料的第一列有2個整數W,N（均不大於100），W代表東西向道路的數目，N代表南北向 道路的數目，編號如上圖所示。接下來的W列代表這W條東西向道路，每列的第一個數為這是第幾條東西向道路，接下來有0個或多個不等的數，代表某些南北向道 路與這條東西向道路相交的十字路口是危險的。
輸入的第一列與第一組測試資料之間，以及各組測試資料之間均有一空白列，第一組Sample Input表示的路如上圖所示，請參考。
輸出說明
每組測試資料輸出一列，為一個整數。代表這個人從左上角走到右下角有多少種不同的走法。
測試資料間亦請空一列。
範例輸入
#1
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
範例輸出
#1
4 0
測資資訊：
記憶體限制：
512
MB
提示 ：
ACM原文題目（需先登入）、Lucky貓中譯題目
出處:
UVa825
[管理者：
taichunmin
(和風信使)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 41015 |
|
d198 | 78 | 2024-06-25 09:31 | |
| 20780 |
|
d198 | 1477 | 2020-03-05 00:53 |