TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1753
  • Problem
  • P1753皇后守卫
    Limits : Time Limit : 10000 MS   Memory Limit : 165536 KB
    Description

    给一个N * M的棋盘,棋盘上的有些格子被打上了标记。现在需要在其中放置尽量少的皇后,使得所有被打上标记的格子至少被某一个皇后攻击或占据到。皇后之间可以互相攻击。

    Input Format

    输入最多15组数据。
    每组数据第一行包含两个整数N和M(1 < N, M < 10),以下为一个N行M列的棋盘,其中打上标记的格子用‘X’表示,其它格子用‘.’表示。
    输入以一个0结尾

    Output Format

    对于每组数据,输出一个数表示最少需要使用的皇后数目。

    Sample Input

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

    Sample Output

    Case 1: 5
    Case 2: 1