塔防遊戲是遊戲的一種類型，進行方式通常是在一個場面上擺設各式各樣的塔，這些塔會自動去攻擊範圍內的敵人。當敵人全部被消滅，或是維持一段時間後沒有被敵人攻陷，就算成功。
現在小莫正在玩一個塔防遊戲，遊戲場景是一個 n × m 的長方形矩陣，裡面有一些障礙物，這些怪物有可能在任何不是障礙物的地方出現，玩家能做的事情就是在四面邊界外設置弓箭塔，這些弓箭塔能夠攻擊所有範圍內出現的怪物，從塔前直到遇到障礙物為止的直線內都是塔的攻擊範圍。
小莫想要讓場面上所有的空地都被至少一個弓箭塔兼顧，請問小莫至少需要在邊界設立幾座弓箭塔。
請注意，弓箭塔的防衛方向只考慮水平和鉛直方向，不考慮斜射，而你至多可以設立 (n+m)×2 座弓箭塔。
第一行有兩個整數 n, m，代表場地的長和寬。
接下來有 n 行，每行有 m 個字元，'x' 代表障礙物，'o' 代表空地。(不含引號)
輸出一個整數，代表小莫至少需要設置幾座弓箭塔，如果不可能兼顧所有空地，輸出 -1。
#test input 1: 6 6 oooooo oooooo oooooo oooooo oooooo oooooo #test input 2: 6 6 xoooox oxxxxo oxxxxo oxxxxo oxxxxo xoooox #test input 3: 3 5 oxooo xoxoo oxooo #test input 4: 2 2 xx xx
#test output 1: 6 #test output 2: 16 #test output 3: -1 #test output 4: 0
flow, graph (CF 2300)
30% 的測資滿足 n = m = 6
30% 的測資滿足 1 ≤ n, m ≤ 300
40% 的測資滿足 1 ≤ n, m ≤ 1000
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||