b062: 1. 城市道路連通網

zerojudeg連結 http://zerojudge.tw/ShowProblem?problemid=b062

內容 ：

若我們在地圖中找出幾個城市之間的道路連通關係，並將其表示為一個無向圖形(undirected graph)；其中，圖形中的節點(node)表示城市，節點與節點間若有直線(edge)連接則代表兩城市間有一直接道路相通。例如：圖一為{c₁,c₂,c₃,c₄,c₅} 五個城市的道路連通圖，圖二為用來記錄此圖一連通圖的相連矩陣(adjacency matrix)，矩陣的1 代表兩節點有一道路相通，否則則以0 表示。

假定在某國家的規劃中，每條道路的長度皆為1 公里。請問如何得知由一城市c_i 到另一個城市c_j 最多不超過N 公里(含N 公里)的走法有幾種?

例如，圖一中由城市c₃ 到城市c₅ 最多不超過3 公里的走法有6 種。包括：1公里1 種 {c₃→c₅}, 2 公里1 種 {c₃→c₄→c₅}, 3 公里4 種{c₃→c₄→c₃→c₅},{c₃→c₅→c₂→c₅}, {c₃→c₅→c₃→c₅},{c₃→c₅→c₄→c₅}。

請注意，這些走法中可包含中途路經目的地的走法，如：上例中的{c₃→c₅→c₂→c₅}等。

輸入說明 ：

第一行為一個正整數m (1<m≤32)，代表城市的個數；即地圖上有{c1, c2, …,

cm}共m 個城市。

接下來的m 行代表相連矩陣中每一行的內容。例如：相連矩陣中的第i 行

第j 列的位置代表c_i 與c_j 兩城市之間有無直接道路相通，其中0 表示兩城市無直

接道路相通，1 表示兩城市間有一個1 公里的道路連接。

接下來三行依序為三個正整數i, j, N (i ≠ j, 1 ≤ i, j ≤ m; 1 ≤ N ≤ 50)，表示由城

市c_i 到另一個城市c_j 最多不超過N 公里。

輸出說明 ：

輸出一整數，表示由城市c_i 到另一個城市c_j 最多不超過N 公里(含N 公里)

的走法有幾種。答案保證不會超過2³¹ − 1。

範例輸入 ：

5

01000

10001

00011

00101

01110

3

5

3

7

0101000

1011000

0100000

1100110

0001010

0001101

0000010

1

7

5

範例輸出 ：

6

11

提示 ：

出處 ：

94全國資訊學科能力決賽

解題策略

使用矩陣乘法