Description
在一个N行M列的二维网格里，有些格子是空地（用字符‘.’表示），有些格子是障碍物（用字符‘#’表示）。每个空地格子都有一只虫子，虫子不会移动。FJ打算用最少的炸弹把所有的虫子消灭。FJ每次可以选择在一个空地格子（不妨假设是格子a）放置一个炸弹，这个炸弹爆炸后，格子a的虫子会被消灭，假设有另一个空地格子b，如果空地格子b同时满足如下两个条件，那么空地b格子的虫子也会被该炸弹消灭：
1.格子a和格子b在同一行或者在同一列。
2.格子a和格子b之间没有障碍物格子。
有趣的是，任意两个不同的空地格子都有且只有一条由空地格子构成的路径，即所有空地格子构成一棵树形结构。注意：炸弹并不能毁灭障碍物！
Input
第一行，两个整数，n和m。1 <= n, m<=50。
接下来是n行m列的二维网格。
Output
输出最少的炸弹数。
Sample Input
输入1：3 4#.....###.##输入2：3 7.#.#.#.........#.#.#.
Sample Output
输出1：
2
输出2：
4
Data Constraint
30%的数据满足空地格子数量小于20
Hint
样例解释1：
#.B.
.B##
#.##
样例解释2：
.#.#.#.
B.B.B.B
.#.#.#.
字符B表示放置炸弹
Solution
树形dp。
找出只有一个方向（上下方向或者左右方向）联通的点作为根。
因为我们要使一个点的所有儿子以及这个点都在同一行或同一列中，这样方便转移。
将同一行中的任意一个点作为当前的根，将其与其他的点连边，用队列维护是否加入树中。
设f[ i ][ 0/1/2 ]表示，以i为根的子树中，子树都炸完了，对于i它自己：
0，这个点不放炸弹，同时它自己不被其他（孩子节）点所炸到。
1，这个点不放炸弹，但是已被某个（孩子节）点所炸到。
2，这个点放炸弹。
表示i的儿子一定不能放炸弹，并且自己必须炸完。
表示某一个儿子放了炸弹（因为儿子与点i是同一行，所以一定能互相炸到），其他随便。
表示当前放了一个炸弹，儿子随意。
初始值：对于叶子结点，f[ i ][ 0 ]=0,f[ i ][ 1 ]=inf,f[ i ][ 2 ]=1。
答案，min(f[root][1/2])