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

##### 发布时间：2023-05-15 09:29:01

``#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...

ps 图灵课堂老师从近一百套最新一线互联网公司面试题中精选而出，涵盖Java架构面试 所有技术栈，包括JVM，Mysql，并发，Spring，Redis，MQ，Zookeeper，Netty， Dubbo，Spring Boot，Spring Cloud，数据结构与算法，设计模式等相关技术领域的大 厂面试题及详解。 详情咨询客服获取全套面经试题。