4639 . κ：砲擊隕石
Description
你是一台搭載雷射大砲的噴射機，負責處理太空基地附近的隕石。你有兩個雷射炮，左邊的會由右上往左下掃射，並將經過的隕石全打爆，反之右邊的砲則是由左上往右下掃射
現在給你 $w \times h$ 的空間，空間中有 $k$ 個隕石。你能找出最有效率的打法，開最少砲擊破所有隕石嗎？
舉個例子，假設一開始的隕石排列如下：
.o..o.
.ooo..
..o...
你可以照這樣的順序開砲：
.o..x.
.oox..
..x...
.x....
.ox...
...x..
..x...
.x....
x.....
這樣就是用三砲把所有隕石解決的一種方法
Input Format
第一行為 $w$ 和 $h$
接下來 $h$ 行每行是 $w$ 個連續字元，代表太空的狀態，o 代表隕石、. 代表沒東西
條件：
$0 < w < 1000$
$0 < h < 1000$
Output Format
最少需要的砲擊數
Sample Input 1
6 3 .o..o. .ooo.. ..o...
Sample Output 1
3
Sample Input 2
8 6 ........ .o..o... .......o ..o..... ........ ..o.ooo.
Sample Output 2
5
Hints
該修圖論了
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 20 |
| 2 | 2~9 | 80 |