切換
舊版
前往
大廳
主題

ZeroJudge - e581: 11067 - Little Red Riding Hood 解題心得

Not In My Back Yard | 2019-12-29 17:37:34 | 巴幣 0 | 人氣 160

題目連結:


題目大意:
給定兩正整數 w 、 h (1 ≦ w 、 h ≦ 100),代表一個 w 行 h 列的地圖網格。小紅帽的家在左下角(0, 0)、奶奶的家在右上角(w, h)。

接著的一列給定一非負整數 n (0 ≦ n ≦ 100),代表大野狼可能出沒的地點之個數。接著有 n 列輸入,每列有兩非負整數 x 、 y (0 ≦ x 、 y ≦ 100),代表大野狼可能出沒的座標(不會出現在小紅帽或是奶奶的家)。

如果每一步,小紅帽只能往網格的右方或上方移動一格。試問,小紅帽有幾條可能的路徑抵達奶奶的家?如果不可能,請輸出「There is no path.」;如果只有一條路,輸出「There is one path from Little Red Riding Hood's house to her grandmother's house.」;否則如果有 X 條路,則輸出「There are X paths from Little Red Riding Hood's house to her grandmother's house.」。



範例輸入:
1 1
0
1 1
2
0 1
1 0
4 4
3
0 1
1 1
3 1
10 10
0
10 10
3
0 1
1 1
1 0
3 3
5
1 0
1 1
1 2
2 2
3 2
0 0


範例輸出:
There are 2 paths from Little Red Riding Hood's house to her grandmother's house.
There is no path.
There are 7 paths from Little Red Riding Hood's house to her grandmother's house.
There are 184756 paths from Little Red Riding Hood's house to her grandmother's house.
There is no path.
There is one path from Little Red Riding Hood's house to her grandmother's house.


解題思維:
定義 Di, j 代表從(0, 0)走到(i, j)的路徑數,可以看到 D0, 0 = 1 。

而對於 i = 0 ,如果(i, 0)有狼出沒,則 Di, 0 = 0 ,反之 Di, 0 =  Di - 1, 0 ;同樣地,如果(i, 0)有狼出沒,則 D0, j = 0 ,反之 D0, j =  D0, j - 1

剩下的可以一列一列(或是一行一行)求,其規則為:
如果有狼在(i, j),則 Di, j = 0 ;
如果沒有狼,則 Di - 1, j +  Di, j - 1

最後,看 Dw, h 之值為何來決定輸出。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作