Codeforces Round #385 (Div. 2) -- B. Hongcow Solves A Puzzle （判断是否是矩形，水题）

大体题意：

给你一个n*m 的矩阵， 你必须用两个相同的图形构建一个矩形，问是否可以？ .表示 这个地方是空地，X是一个小元素！你不能旋转盖子， 整体只能移动！

思路：

这个问题一开始理解错了，被hack了。事实上，移动 只能整体移动！

因此 只需要判断这个图是否是矩形！

详见代码：

#include <bits/stdc++.h>#define ps push_back#define fi first#define se second#define mr make_pairusing namespace std;typedef long long ll;typedef unsigned long long LLU;const int inf = 0x3f3f3f3f;const double eps = 1e-10;const double pi = acos(-1.0);const int maxn = 1000 + 10;char s[maxn][maxn];int main(){    int n, m;    scanf("%d %d",&n, &m);    for (int i = 0; i < n; ++i)scanf("%s",s[i]);    int l = inf,r = -inf,u = inf,d = -inf;    for (int i = 0; i < n; ++i){        for (int j = 0; j < m; ++j){            if (s[i][j] == 'X'){                l = min(l,j);                r= max(r,j);                u = min(u,i);                d = max(d,i);            }        }    }    bool ok = 1;    for (int i = u; i <= d; ++i){        for (int j = l; j <= r; ++j){            if (s[i][j]!='X')ok = 0;        }    }    if (ok)puts("YES");    else puts("NO");    return 0;}

B. Hongcow Solves A Puzzle

time limit per test

memory limit per test

input

output

Hongcow likes solving puzzles.

nbymgrid of characters, where the character 'X' denotes a part of the puzzle and '.' denotes an empty part of the grid. It is guaranteed that the puzzle pieces are one 4-connected piece. See the input format and samples for the exact details on how a jigsaw piece will be specified.

cannot rotate or flipthe puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces alsocannot overlap.

X' from different pieces can share the same position.

Input

nandm(1 ≤ n, m ≤ 500), the dimensions of the puzzle piece.

nlines will describe the jigsaw piece. Each line will have lengthmand will consist of characters '.' and 'X' only. 'X' corresponds to a part of the puzzle piece, '.' is an empty space.

X' character in the input and that the 'X' characters form a 4-connected region.

Output

YES" if it is possible for Hongcow to make a rectangle. Output "NO" otherwise.

Examples

input

2 3XXXXXXX

output

YES

input

2 2.XXX

output

NO

input

5 5...X...

output

YES

Note

For the first sample, one example of a rectangle we can form is as follows

111222111222

For the second sample, it is impossible to put two of those pieces without rotating or flipping to form a rectangle.

In the third sample, we can shift the first tile by one to the right, and then compose the following rectangle:

...XX...