回分類題庫
z024: 捷運路線
關鍵字: npsc模擬試題

測資點 : 1 | Time Limit : 2000 ms | Memory Limit : 128000 KB
Accepted : 5 Times / 5 Users | Submit : 6 Times / 5 Users | Accepted rate : 100%
題目加入時間 : 2018-10-02 12:48

Content: 简体中文

螞蟻們討厭環狀的東西,所以螞蟻城裡的捷運不會出現環狀線的捷運。特別的是,螞蟻城裏的捷運都是沿著東西或南北向前進。也就是說,每次捷運轉彎都是直接轉90 度的直

秉持著年開通條線的原則,捷運路線網越來越複雜了。且每新增條路線,就會造成更多的負擔。於是,在若年後的今天,螞蟻城的⾸⻑打算好好整治下現在紛亂的捷運路線。

條捷運的路線,都會從某個起點出發,然後沿著軌道不重複地經過些站,抵達終點。為什麼要不重複呢?因為如果有重複經過同站的話,搭捷運的螞蟻們便會覺得浪費時間,尤其是在這個沒有環狀路線的交通路網上。

請你幫忙算算,少需要幾條不同的捷≤運路線,才能使得每段軌道上都少有條捷運路線經過?

Input:

的第⼀⾏個正整數(T 100),代表測試資料的組數。

組測試資料有兩個正整數n , m (1 ≤ n , m 100),中間以個空隔開。接下來有n ⼀⾏m 的字串。這些字串組成了張螞蟻城現在的捷運路網圖。

圖上的意義如下:

井字號 ( '# ' ),表捷運的軌道。
點 ( ' . ' ),代表這個位置沒有東西。
⼤⼩寫英,代表這是站。可能有許多不同的站標著相同的英符號。

保證對於任何個軌道,它緊鄰的四格恰好有兩個字元是軌道或捷運站。

保證不會有兩個捷運站緊緊相鄰,且每個捷運站周圍的四格之中,少有格是軌道。

Output:

對於每組測試資料請輸出⼀⾏,包含個整數最少需要幾條不同的捷運線,才能讓任何段軌道都有列經過

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
4 15
......##B#....C
.....##..#.####
....##...###...
.A###..........
5 7
A###.D#
...#..#
.F.C##b
.#.#...
.##D...

Sample Output :

1
2

Hint :

2014npsc模擬試題

Author :

npsc模擬試題 (管理員:Chang)

  Solve it!   Status Forum