塔防遊戲 1 (towerdefense1)
塔防遊戲是遊戲的一種類型,進行方式通常是在一個場面上擺設各式各樣的塔,這些塔會自動去攻擊範圍內的敵人。
當敵人全部被消滅,或者維持一段時間而沒有被敵人攻陷,就算成功。
現在小莫正在玩一個塔防遊戲,遊戲場景是一個6 × 6的正方形矩陣,裡面有一些障礙物。 怪物有可能在任何不是障礙物的地方出現,玩家能做的事情就是在四面邊界設置弓箭塔, 這些弓箭塔能夠攻擊所有範圍內出現的怪物,從塔前直到遇到障礙物為止的直線內都是塔 的攻擊範圍。
小莫想要讓場面上所有的空地都能夠被至少一個弓箭塔兼顧,請問小莫至少需要在邊界設置幾座弓箭塔呢?
註:弓箭塔防衛的方向,只考慮水平或垂直方向,不考慮斜射(如以下範例 2 圖示)
輸入格式
共 6 行,每行 6 個字元,「.」代表空地,「#」代表障礙物。
輸出格式
請輸出一個整數於一行,代表小莫至少需設置幾座弓箭塔。 如果不可能兼顧所有空地,請輸出「-1」。
範例輸入 1
......
......
......
......
......
......
範例輸出 1
6
範例輸入 2
#....#
.####.
.####.
.####.
.####.
#....#
範例輸出 2
16
範例輸入 3
......
......
..#...
.#.#..
..#...
......
範例輸出 3
-1
提示
範例 1 說明: 場面上沒有任何障礙物,四面邊界任選一個擺滿 6 個弓箭塔即可監視所有空地。 範例 2 說明: 場面上共有 16 個空地,上下左右各 4 個: 看守左邊的空地需要在左邊界設置 4 個弓箭塔, 看守上面的空地需要在上邊界設置 4 個弓箭塔, 右邊和下面以此類推, 總共需要 16 個弓箭塔。 範例 3 說明: 第 4 行第 3 列的空地被障礙物圍住,不管弓箭塔擺哪裡都無法攻擊到,因此無解。
留言