題目連結：
題目大意：
輸入有多筆測試資料。每筆測資第一列給定兩正整數 N 、 M （1 ≦ N 、 M ≦ 50），代表有一個 N 列 M 行的地圖。接著有 N 列的輸入，每列給定 M 個整數。每個整數只會是 0 或是 1，前者代表空地、後者代表有障礙物無法通行。
接著的一列再給定四整數 Sx 、 Sy 、 Ex 、 Ey （0 ≦ Sx 、 Ex < N ， 0 ≦ Sy 、 Ey < M），代表起點所在的列數以及行數和終點所在的列數以及行數。試問從 (Sx, Sy) 走到 (Ex, Ey) 的最短路徑有多少條？因為答案可能很大，所以請取除以 100000 的餘數後輸出。
範例輸入：
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 4 4
6 5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 0 1 1 0
0 1 1 0 0
0 0 0 0 0
0 4 5 0
6 5
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0
0 4 5 0
範例輸出：
70
3
6
解題思維：
有點像這題，就是用廣度優先搜尋（Breadth First Search，BFS）的精神去從起點慢慢擴張到終點。
從起點開始，每次擴張就是看當前格子的周遭四格。沒有障礙且「沒有看過」的格子就加進一個佇列（Queue）裡去等待之後的探訪，並將該格設為「有看過」。
而因為這樣子擴張保證了起點到當前格子是最短路徑，因此此時該格子的最短路徑之數量即是其周遭四格當前的最短路徑數量之總和（在先前的格子都會被探訪，所以最短路徑數量已知，而其後的格子應為還沒探訪，所以路徑數為 0）。
整張地圖擴張完後，即可得終點的最短路徑數量。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
