B. Tiling Challenge

- 日理万妓 2022-04-25 01:18 142阅读 0赞

B. Tiling Challenge

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

One day Alice was cleaning up her basement when she noticed something very curious: an infinite set of wooden pieces! Each piece was made of five square tiles, with four tiles adjacent to the fifth center tile:

![1303515e52020acada6b9cb59c6722e3bd1a55a5.png][]

By the pieces lay a large square wooden board. The board is divided into n2n2 cells arranged into nn rows and nn columns. Some of the cells are already occupied by single tiles stuck to it. The remaining cells are free.

Alice started wondering whether she could fill the board completely using the pieces she had found. Of course, each piece has to cover exactly five distinct cells of the board, no two pieces can overlap and every piece should fit in the board entirely, without some parts laying outside the board borders. The board however was too large for Alice to do the tiling by hand. Can you help determine if it's possible to fully tile the board?

Input

The first line of the input contains a single integer nn (3≤n≤503≤n≤50) — the size of the board.

The following nn lines describe the board. The ii-th line (1≤i≤n1≤i≤n) contains a single string of length nn. Its jj-th character (1≤j≤n1≤j≤n) is equal to "." if the cell in the ii-th row and the jj-th column is free; it is equal to "\#" if it's occupied.

You can assume that the board contains at least one free cell.

Output

Output YES if the board can be tiled by Alice's pieces, or NO otherwise. You can print each letter in any case (upper or lower).

Examples

input

Copy

3
    #.#
    ...
    #.#

output

Copy

YES

input

Copy

4
    ##.#
    #...
    ####
    ##.#

output

Copy

input

Copy

5
    #.###
    ....#
    #....
    ###.#
    #####

output

Copy

YES

input

Copy

5
    #.###
    ....#
    #....
    ....#
    #..##

output

Copy

Note

The following sketches show the example boards and their tilings if such tilings exist:

![6667e560f362349f0a92b0fcffb87009e8b6f65a.png][]

题意：给了一个n\*n的矩形，上面有'\#'和'.'两种，'\#'表示已经填了东西了，点点表示是空的，需要填充，能不能用那种中间一块瓷砖和四周各一块的瓷砖填满这个这个矩形。

题解：模拟 从第一点开始遍历，如果是点就判断能不能放这种五个方块的瓷砖，假设当前瓷砖坐标是i,j，另外四块肯定是（）i+1,j）,（i+2,j）,(i+1,j-1),(i+1,j+1)，如果能放，就填充进去，把点点变为\#，不能放就输出no退出。

#include<bits/stdc++.h>
    using namespace std;
    int n;
    char m[55][55];
    void judge(int x,int y)
    {
        if(x<1||x>n||y<1||y>n||m[x][y]=='#')
        {
            puts("NO");
            exit(0);
        }
        m[x][y]='#';
    }
    int main()
    {
        cin>>n;
        for(int i=1; i<=n; i++)
            scanf("%s",m[i]+1);
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
            {
                if(m[i][j]=='.')
                    judge(i,j),judge(i+1,j),judge(i+2,j),judge(i+1,j-1),judge(i+1,j+1);
            }
            puts("YES");
        return 0;

[1303515e52020acada6b9cb59c6722e3bd1a55a5.png]: /images/20220210/4fda4c2119c74eef986fa9f473fb8663.png
[6667e560f362349f0a92b0fcffb87009e8b6f65a.png]: /images/20220210/30edbf1ca8344015a9fa132472776527.png