c056: 塔防遊戲 1 (towerdefense1)
Tags : 列舉
Accepted rate : 1人/1人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-04-30 18:40

Content

塔防遊戲是遊戲的一種類型,進行方式通常是在一個場面上擺設各式各樣的塔,這些塔會自動去攻擊範圍內的敵人。

當敵人全部被消滅,或者維持一段時間而沒有被敵人攻陷,就算成功。

現在小莫正在玩一個塔防遊戲,遊戲場景是一個6 × 6的正方形矩陣,裡面有一些障礙物。 怪物有可能在任何不是障礙物的地方出現,玩家能做的事情就是在四面邊界設置弓箭塔, 這些弓箭塔能夠攻擊所有範圍內出現的怪物,從塔前直到遇到障礙物為止的直線內都是塔 的攻擊範圍。

小莫想要讓場面上所有的空地都能夠被至少一個弓箭塔兼顧,請問小莫至少需要在邊界設置幾座弓箭塔呢?

註:弓箭塔防衛的方向,只考慮水平或垂直方向,不考慮斜射(如以下範例 2 圖示)

Input

共 6 行,每行 6 個字元,「.」代表空地,「#」代表障礙物。

Output

請輸出一個整數於一行,代表小莫至少需設置幾座弓箭塔。 如果不可能兼顧所有空地,請輸出「-1」。

Sample Input
// 1
......
......
......
......
......
......

// 2
#....#
.####.
.####.
.####.
.####.
#....#
// 3
......
......
..#...
.#.#..
..#...
......
Sample Output
// 1
6
// 2
16
// 3
-1
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1K
公開 測資點#3 (10%): 1.0s , <1K
公開 測資點#4 (10%): 1.0s , <1K
公開 測資點#5 (10%): 1.0s , <1K
公開 測資點#6 (10%): 1.0s , <1K
公開 測資點#7 (10%): 1.0s , <1K
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
Hint :

範例 1 說明:

場面上沒有任何障礙物,四面邊界任選一個擺滿 6 個弓箭塔即可監視所有空地。

範例 2 說明:

場面上共有 16 個空地,上下左右各 4 個: 看守左邊的空地需要在左邊界設置 4 個弓箭塔, 看守上面的空地需要在上邊界設置 4 個弓箭塔, 右邊和下面以此類推, 總共需要 16 個弓箭塔。

範例 3 說明:

第 4 行第 3 列的空地被障礙物圍住,不管弓箭塔擺哪裡都無法攻擊到,因此無解。

Tags:
列舉
出處:
YTP2020 [管理者:
810848 (路過)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」