守卫键盘 Guarding the Chessboard

题意翻译

输入一个$n×m$ 的棋盘（$n,m<10$ ），某些格子有标记。用最少的皇后守卫（即占据或者攻击）所有带标记的格子。 Translated by @_UKE自动机_

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2155 [PDF](https://uva.onlinejudge.org/external/112/p11214.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11214/b944da1eec66e12583384f5364ec48727533152a.png)

输入输出格式

输入格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11214/8c120f1a504f35395db88fd3955c4ce2bf076acf.png)

输出格式

![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA11214/009a0b1494af956275aeea5844527ab58e8de10e.png)

输入输出样例

输入样例 #1

8 8
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
XXXXXXXX
8 8
X.......
.X......
..X.....
...X....
....X...
.....X..
......X.
.......X
0

输出样例 #1

Case 1: 5
Case 2: 1