TopCoder

Caido
$\mathbb{W}\mathcal{aimai}\sim$

User's AC Ratio

98.5% (65/66)

Submission's AC Ratio

71.1% (108/152)

Tags

Description

若我們在地圖中找出幾個城市之間的道路連通關係,並將其表示為一個無向圖形(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→c4}。
請注意,這些走法中可包含中途路經目的地的走法,如:上例中的{c3→c5→c2→c5}等。

Input Format

第一行為一個正整數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 公里。

Output Format

輸出一整數,表示由城市ci 到另一個城市cj 最多不超過N 公里(含N 公里)
的走法有幾種。

答案保證不會超過231 − 1。

Sample Input 1

5
01000
10001
00011
00101
01110
3
5
3

Sample Output 1

6

Sample Input 2

7
0101000
1011000
0100000
1100110
0001010
0001101
0000010
1
7
5

Sample Output 2

11

Hints

Problem Source

原TIOJ1146 / 94全國賽(prob 1)。

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 900 65536 262144 1
1 900 65536 262144 2
2 900 65536 262144 3
3 900 65536 262144 4
4 900 65536 262144 5