回分類題庫
d027: 2008 程式達人 A - 地圖搜尋
出處:

Difficulity : 1
Accepted : 17 Times | Submit :44 Times | Clicks : 1733
Accepted : 10 Users | Submit : 10 Users | Accepted rate : 100%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2008-10-10 10:24

Content :

給定任意地圖的通道資料,找出符合某一通行條件的城市。

Input :

輸入資料包含一份地圖資料,以一個任意大小的方陣來表示某一地區主要地點間的有方向性的聯繫通道的存在與否。令 Li 和 Lj 分別代表一個區域中編號第 i 個和第 j 個的城市(請注意,城市的編號將從 1 開始),再令 mi, j 是一個方陣 裡面第 i 列第 j 行的成員,如果 Li 有一條通道直接通往 Lj 則 mi, j 是1,否則 mi, j 是 0。

本程式須要找出有哪一些城市可以經過某一特定「旅次」而可以到達某一特定城市。在計算旅次時,只要離開目前城市,不管前往哪一個城市(即使是本身)也算一個旅次。舉例來說,如果因為某一些特殊原因,我們可以從 Lk 出發又直接回到 Lk 的話(註:前提是 mk, k必須是 1),這樣表面上沒有改變結果的旅行也算是一個旅次。因此,如果有一個行程是從城市 A 到城市 B 又到城市 B 再到城市 C 又到城市 C 的話,則雖然只有歷經三個城市但是算是經過四個旅次(即 A → B, B → B, B → C, C → C)。

給定以上地圖,本程式須要找出經過特定旅次之後,可以到達指定城市的那一些城市之中,哪一些城市的可選擇路線數目還超過所指定的門檻值。

基於以上說明,輸入資料將包含一個任意大小的方陣,還有另一筆資料來指定問題。指定問題的資料只有三個數字,第一個數字是目標城市的編號,第二個數字則是所要經過的精確旅次數目,第三個數字則是路線數目的門檻值。

以下是一個簡明的範例。這一份地圖只有三個城市和三個通道,即第一個城市可以直接到第二個城市、第二個城市可以直接到第三個城市、第三個城市可以直接到第一個城市。如果我們原本是在第一個城市,經過三個旅次之後,我們會回到第一個城市。在這一個簡單的區域中,我們只有一個方法,經過三個旅次,可以從第一個城市到第一個城市(請先忽略我們為什麼有這樣的需求的合理性)。

| 0 1 0 |
| 0 0 1 |
| 1 0 0 |

Output :

依照輸入說明,程式的輸出非常簡單,就是符合條件的城市編號。為了方便檢驗輸出結果,請由小到大輸出符合搜尋條件的城市編號。(請注意,城市的編號將從 1 開始)

Sample Input :

0 1 1 0 1
1 1 1 0 0
1 0 1 0 1
0 1 0 1 0
0 0 1 1 1
4 3 3

Sample Output :

3 5

Hint :

解題率:1/19

Author :

(管理員:MrWrongAnswer)

  Solve it!   Status Forum (2)

C++
C
JAVA
55268. johnny (4 ms , 253KB)
40017. cp99303052 (6 ms , 476KB)
55185. johnny (8 ms , 238KB)
36816. nothinglo (8 ms , 462KB)
29670. henryokc (8 ms , 397KB)
55388. ag100 (1 ms , 250KB)
1893. yuhanlyu (1 ms , 266KB)
39311. king_of_laba (2 ms , 246KB)
1895. yuhanlyu (2 ms , 262KB)
1894. yuhanlyu (2 ms , 269KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡