Time Limit: 5 second(s) | Memory Limit: 32 MB |
Walter White finally discovered the medicine for a dangerous disease. That's why he is in danger, because some people are targeting him to get the formula. So, now he and his co-workers have to leave the city.
Assume that the city can be modeled as an M x N grid, where a cell containing a '*' means that a co-worker lives in that place, a cell containing a '.' means it's empty.
So, Walter informed all of them by phone to leave the city at once and he has laid down a rule that no one will cross path in their way out of the city. Since if two or more persons meet at same cell (even in the boundary cells), there is a big possibility that they all might get caught. Walter doesn't want that, so he needs to know whether all of them can get out of the city. So, he asked you to help him.
For simplicity, assume that if one person reaches any of the border cells of the grid, he is considered to be out of the city. And from any cell, a person can move only to its four adjacent cells (north, south, east or west).
Fig 1: Position of the persons |
Fig 2: Escape Paths |
For example, for the given 7 x 6 grid, the colored circles show the position of the persons who are escaping (fig 1). And a feasible solution is shown in fig 2.
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with a line containing two integers M and N (1 ≤ M, N ≤ 100). Each of the next M lines contains N characters denoting the map. Each characters is either '.' or '*'. Total number of persons in a map will be at most 2*(M+N).
For each case, print the case number and 'yes' if it's possible for them to get out of the city maintaining the restrictions. Otherwise print 'no'.
Sample Input |
Output for Sample Input |
3 7 6 ..*... .*.*.. ..*.*. ***..* .....* ..**.. ....*. 4 10 ***..***.* *.**.***.* ..*..*..** .**.*.*.** 4 10 ***..***.* *.**.***.* ..*..*...* .**.*.*.** |
Case 1: yes Case 2: no Case 3: yes |
Developed and Maintained by
JANE ALAM JAN |
Copyright © 2012
LightOJ, Jane Alam Jan |