H :: Minesweeper

Time Limit: 10 Seconds    Memory Limit: 131072 KB

It is not surprising that you have played the Minesweeper game at least once. In this game, the player is initially presented with a grid (minefield) of squares.  Some randomly selected squares, unknown to the player, are designated to contain mines. A square is unsafe if it contains a mine. Otherwise, it is called safe. The game is played by revealing the squares of the grid, typically by mouse clicks. If an unsafe square is revealed, the player loses the game. Otherwise, a digit is revealed in the safe square, indicating the number of adjacent squares (out of the possible eight) that are unsafe. In typical implementation, if this number is zero, the square appears blank, and the surrounding squares are automatically also revealed. In a variant of this game, the number of unsafe squares is given at the beginning of the game but in our variant this number is hidden. The player wins if he can reveal all safe squares. For a given minefield, your job is to find out whether the minefield can be deterministically cleaned with starting from the given start square, i.e. until all  safe squares are not revealed, at each step we can find more safe squares just using the numbers appearing on revealed squares (not by clicking squares randomly.) 

Input

There are multiple test cases in the input. Each test case starts with a line containing two non-negative integers n and m not exceeding 10 where n and m are the number of rows and columns of the minefield.  Each of the next n lines contains a string of size m consisting of {‘+’, ‘*’, ‘-’}. Character ‘-’ denotes a blank square, ‘*’ denotes an unsafe square and ‘+’ denotes the starting square which by default is safe. There is exactly one ‘+’ in each test case. The input terminates with “0 0” which should not be processed.

Output

For each test case, output “Yes” if the given minefield can be deterministically cleaned. Otherwise, output “No”.

Sample Input

1 3
-+*
3 4
*--+
**--
*--*
3 4
***-
*---
*--+
0 0

Sample Output

No
No
Yes

Submit

Source: 11th Iran Nationwide Internet Contest