UVA-11067 - Little Red Riding Hood

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20170328 大學程式能力檢定 CPE」題目。
• 相同題目：NCTU-11226

題意概要

題目情境為小紅帽的故事，但和我們所知的故事有點出入，這次小紅帽沒有獵人的拯救，小紅帽必須要獨自躲避大野狼，成功抵達小紅帽的奶奶家。題目假設從小紅帽家到奶奶家的地圖為一個矩形的棋盤，其中最左下角為小紅帽家，而最右上角為奶奶家，而大野狼會埋伏在這之中的座標點上。題目會先給定該筆測資的棋盤大小為 $(w, h)$，並且給定 $N$ 筆大野狼埋伏的座標 $(x, y)$，請求出小紅帽可以成功抵達奶奶家的所有路徑數。

• 分析：本題為動態規劃 (Dynamic Programming; DP) 的簡單題型。在初始化棋盤大小後，並依照題目意思將大野狼的座標位置標記為 $-1$，在探索的路徑的過程中，將左下角的起始座標的值令為 $1$，如果該做標點的值為 $-1$，則令為 $0$，表示沒有辦法經過該做標點，反之如果不是 $-1$，則將該點做標的值令為相鄰前一步座標的值之總和。

  $\begin{align*} path(i, j) = \left\{\begin{array}{ll} 1, & \mbox{if $i = 0$ and $j = 0$} \\ path(i, j - 1), & \mbox{if $i = 0$} \\ path(i - 1, j), & \mbox{if $j = 0$} \\ path(i, j - 1) + path(i - 1, j) & \mathrm{otherwise.} \end{array} \right. \end{align*}$

  • 此題要記得使用 long long int。

Input

There will be several testcases. The grid’s width $w$, $1 \le w \le 100$, and grid’s height $h$, $1 \le h \le 100$, are on the first line. The last testcase will contain a $0$ for height $h$ and a $0$ for the width $w$ and should not be processed. In the next line there follows the number $n$, $0 \le n \le 100$ of the wolf’s possible locations. The next $n$ lines contain two integers each. The first denoting the wolf’s $x$, $0 \le x \le 100$ coordinate, the second the wolf’s $y$, $0 \le y \le 100$ coordinate. Little Red Riding Hood’s House is at the point $(0, 0)$ and the grandmother’s house is at $(w, h)$. The wolf cannot be at either house.

Output

Output one line for each testcase. If there is more than one path between Little Red Riding Hood’s house and the grandmother’s house on which Little Red Riding Hood doesn’t meet the wolf and only moves right and upwards, output the number of paths in the format: There are X paths from Little Red Riding Hood’s house to her grandmother’s house. If there is exactly one path print: There is one path from Little Red Riding Hood’s house to her grandmother’s house. Otherwise print: There is no path. The number of paths will always be $\le 2^32 − 1$.

Sample Input

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

Sample Output

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.