內容
若我們在地圖中找出幾個城市之間的道路連通關係，並將其表示為一個無向圖形(undirected graph)；其中，圖形中的節點(node)表示城市，節點與節點間若有直線(edge)連接則代表兩城市間有一直接道路相通。例如：圖一為{c1,c2,c3,c4,c5} 五個城市的道路連通圖，圖二為用來記錄此圖一連通圖的相連矩陣(adjacency matrix)，矩陣的1 代表兩節點有一道路相通，否則則以0 表示。
假定在某國家的規劃中，每條道路的長度皆為1 公里。請問如何得知由一城市ci 到另一個城市cj 最多不超過N 公里(含N 公里)的走法有幾種?
例如，圖一中由城市c3 到城市c5 最多不超過3 公里的走法有6 種。包括：1公里1 種 {c3→c5}, 2 公里1 種 {c3→c4→c5}, 3 公里4 種{c3→c4→c3→c5},{c3→c5→c2→c5}, {c3→c5→c3→c5},{c3→c5→c4→c5}。
請注意，這些走法中可包含中途路經目的地的走法，如：上例中的{c3→c5→c2→c5}等。
輸入說明
第一行為一個正整數m (1<m≤32)，代表城市的個數；即地圖上有{c1, c2, …,
cm}共m 個城市。
接下來的m 行代表相連矩陣中每一行的內容。例如：相連矩陣中的第i 行
第j 列的位置代表ci 與cj 兩城市之間有無直接道路相通，其中0 表示兩城市無直
接道路相通，1 表示兩城市間有一個1 公里的道路連接。
接下來三行依序為三個正整數i, j, N (i ≠ j, 1 ≤ i, j ≤ m; 1 ≤ N ≤ 50)，表示由城
市ci 到另一個城市cj 最多不超過N 公里。
cm}共m 個城市。
接下來的m 行代表相連矩陣中每一行的內容。例如：相連矩陣中的第i 行
第j 列的位置代表ci 與cj 兩城市之間有無直接道路相通，其中0 表示兩城市無直
接道路相通，1 表示兩城市間有一個1 公里的道路連接。
接下來三行依序為三個正整數i, j, N (i ≠ j, 1 ≤ i, j ≤ m; 1 ≤ N ≤ 50)，表示由城
市ci 到另一個城市cj 最多不超過N 公里。
輸出說明
輸出一整數，表示由城市ci 到另一個城市cj 最多不超過N 公里(含N 公里)
的走法有幾種。答案保證不會超過231 − 1。
的走法有幾種。答案保證不會超過231 − 1。
範例輸入
#1
5 01000 10001 00011 00101 01110 3 5 3 7 0101000 1011000 0100000 1100110 0001010 0001101 0000010 1 7 5
範例輸出
#1
6 11
測資資訊：
記憶體限制：
512
MB
提示 ：
標籤:
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||