B. Plus from Picture

time limit per test: 1 second
memory limit per test: 256 megabytes
input: standard input
output: standard output

You have a given picture with size w×hw×h. Determine if the given picture has a single “+” shape or not. A “+” shape is described below:

  • A “+” shape has one center nonempty cell.
  • There should be some (at least one) consecutive non-empty cells in each direction (left, right, up, down) from the center. In other words, there should be a ray in each direction.
  • All other cells are empty.

Find out if the given picture has single “+” shape.

Input

The first line contains two integers hh and ww (1h1≤hw500w≤500) — the height and width of the picture.

The ii-th of the next hh lines contains string sisi of length ww consisting “.” and “*” where “.” denotes the empty space and “*” denotes the non-empty space.

Output

If the given picture satisfies all conditions, print “YES“. Otherwise, print “NO“.

You can output each letter in any case (upper or lower).

Examples

Input

Output

Input

Output

Input

Output

Input

Output

Input

Output

Input

Output

Note

In the first example, the given picture contains one “+“.

In the second example, two vertical branches are located in a different column.

In the third example, there is a dot outside of the shape.

In the fourth example, the width of the two vertical branches is 22.

In the fifth example, there are two shapes.

In the sixth example, there is an empty space inside of the shape.


本题为简单模拟题,甚至不涉及图论相关知识

题意大致为要求一个图片只能有一个‘+’号,并且除去这个+号以外的所以图像均为空图

大致思路也很好想到,大致就是先寻找到一个‘+’号

然后除掉中心点向外辐射的就可以了

方法大概就是把这个中心点连接的’*’都变成’.’

只要注意一下全是空的情况就行了

(虽然我WA了,后来补题的时候才A的)

(还是因为break没有break二重循环才WA的)

(枯辽)






2019-06-12  00:05:53  Author: WindCry1




0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注