● Codeforces Round #228 (Div. 2) - B. Fox and Cross

قلی یک جدول n*n دارد که روی هر خانه از آن با یکی از دو نماد "." یا "#" علامت گذاشته شده است. صلیب، شکلی است که از قرار گرفتن 5 خانه کنار همدیگر به شکل زیر به دست می آید:

قلی می خواهد تعدادی صلیب روی این جدول بکشد (ممکن است صفر باشد) به طوری که هر خانه ی آن، یک نماد "#" را پوشش دهد، در ضمن هیچ دو صلیبی خانه ی مشترک نداشته باشند.

شما وظیفه دارید به او بگویید که آیا می تواند با تعدادی صلیب، تمام "#" های جدول را بپوشاند به طوری که شروط بالا نیز رعایت شوند؟

input

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

output

YES

ورودی:

خط اوّل ورودی عدد صحیح (n (3 ≤ n ≤ 100 نشان دهنده ی سایز جدول است. در n خط بعدی، در هر خط n کاراکتر "." یا "#"  داده می شود.

خروجی:

اگر "#" های موجود در جدول داده شده را می توان با تعدادی صلیب پوشاند، عبارت "YES" و در غیر اینصورت "NO" را چاپ کنید.

بررسی مثال بالا: شما می توانید با 2صلیب، کل علامت های "#" را بپوشانید که در تصویر زیر مشهود است:

این تضمین شده است که تمامی کاراکترها از دو حالت "." یا "#" خارج نیستند.

// A Drop of the Programming Sea - adops.blog.ir

#include <algorithm>
#include <iostream>
using namespace std;

bool ck[150][150];

int main()
{
    int n;
    cin >> n;
    char **a = new char*[n+2];
    for(int i=0; i<2+n; i++)
        a[i] = new char[2+n];

    for(int i=0; i<n+2; i++)
    {
        a[i][0] = '.';
        a[0][i] = '.';
        a[n+2-1][i] = '.';
        a[i][n+2-1] = '.';
        ck[i][0] = true;
        ck[0][i] = true;
        ck[n+2-1][i] = true;
        ck[i][n+2-1] = true;
    }
    
    int c=0;
    for(int i=1; i<n+1; i++)
        for(int j=1; j<n+1; j++)
        {
            cin >> a[i][j];
            if(a[i][j] == '#')
                c++;
        }

    for(int i=1; i<n+1; i++)
        for(int j=1; j<n+1; j++)
            if(a[i][j]=='#' && !ck[i][j])
            {
                ck[i][j] = true;
                if((a[i][j+1]=='#' && a[i][j-1]=='#' && a[i+1][j]=='#' && a[i-1][j]=='#') && (!ck[i][j+1] && !ck[i][j-1] && !ck[i+1][j] && !ck[i-1][j]))
                {
                    ck[i][j+1]=true;
                    ck[i][j-1]=true;
                    ck[i+1][j]=true;
                    ck[i-1][j]=true;
                }
                else ck[i][j] = false;
            }

    int t=0;
    for(int i=1; i<n+2-1; i++)
        for(int j=1; j<n+2-1; j++)
            if(ck[i][j])
                t++;
                
    if(t == c)
        cout << "YES\n";
    else
        cout << "NO\n";
}