Game of Eliminate
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 0 Accepted Submission(s): 0
Problem Description
Little Ruins is a studious boy, but in rest time, he will play some little game.
Today he found a game of eliminate: there is $N \times M$ tiles which only contains '#' and '*', you have two patterns to eliminate tiles:
:.
and
.:
Each step you can use a pattern and eliminate tiles on the bottom two lines. After each step,the tiles above eliminated tiles will fall down.
Your goal is to eliminate all '*' tiles, please calculate the minimum steps.
Today he found a game of eliminate: there is $N \times M$ tiles which only contains '#' and '*', you have two patterns to eliminate tiles:
:.
and
.:
Each step you can use a pattern and eliminate tiles on the bottom two lines. After each step,the tiles above eliminated tiles will fall down.
Your goal is to eliminate all '*' tiles, please calculate the minimum steps.
Input
First line contains an integer $T$, which indicates the number of test cases.
Every test case begins with two integers $N$ and $M$, which indicates the size of tiles.
In the following N lines, every line contains $M$ characters means the type of tiles.
Limits
$1 \leq T \leq 50$.
$1 \leq N \leq 2000$
$2 \leq M \leq 2000$.
For 80% of the use cases, $1 \leq N, M \leq 100$ holds.
Every test case begins with two integers $N$ and $M$, which indicates the size of tiles.
In the following N lines, every line contains $M$ characters means the type of tiles.
Limits
$1 \leq T \leq 50$.
$1 \leq N \leq 2000$
$2 \leq M \leq 2000$.
For 80% of the use cases, $1 \leq N, M \leq 100$ holds.
Output
For every test case, you should output 'Case #x: y', where x indicates the case number and counts from 1 and y is the result.
Sample Input
1 3 2 #* *# ##
Sample Output
Case #1: 2