HYSBZ - 3750 Pieczęć（模拟）

题目：

一张n*m的方格纸，有些格子需要印成黑色，剩下的格子需要保留白色。

你有一个a*b的印章，有些格子是凸起（会沾上墨水）的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求：

（1）印章不可以旋转。

（2）不能把墨水印到纸外面。

（3）纸上的同一个格子不可以印多次。

思路：

可以先把印章中的凸起先提取出来单独存储，然后遍历这张方格纸，如果遇上x就把存起来的凸起印刷到方格纸上，印刷过程中如果遇到出界、方格纸不是x或者已经印刷过的情况，就是不能完成印刷。

如果全部印刷完就是成功。

代码：

#include <bits/stdc++.h>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <vector>

#include <algorithm>

#include <queue>

#define MAX 1000000000

#define inf 0x3f3f3f3f

#define FRE() freopen("in.txt","r",stdin)

using namespace std;

typedef unsigned long long ll;

const int maxn = ;

char paper[maxn][maxn],board[maxn][maxn];

int vis[maxn][maxn];

int n,m,a,b;

vector<pair<int,int> > pi;

bool isin(int x,int y)

{

    return x>= && x<n && y>= && y<m;

}

bool solve()

{

    for(int i=; i<n; i++)

    {

        for(int j=; j<m; j++)

        {

            if(paper[i][j]=='x' && !vis[i][j])//对纸张上出现的x进行一次印章印刷

            {

                for(int k=; k<pi.size(); k++)

                {

                    int tx = i+pi[k].first, ty = j+pi[k].second;

                    if(isin(tx,ty) && !vis[tx][ty] && paper[tx][ty]=='x')

                        vis[tx][ty]++;

                    else//如果遇到不符合的情况就不能完成印刷

                        return false;

                }

            }

        }

    }

    return true;

}

int main()

{

    //FRE();

    int kase;

    scanf("%d",&kase);

    while(kase--)

    {

        pi.clear();

        memset(vis,,sizeof(vis));

        scanf("%d%d%d%d",&n,&m,&a,&b);

        for(int i=; i<n; i++)

            scanf("%s",paper[i]);

        bool isfirst = true;

        for(int i=; i<a; i++)

        {

            scanf("%s",board[i]);

            for(int j=; j<b; j++)//提取出印章上所有的凸起

            {

                if(board[i][j]=='x' && isfirst)

                {

                    pi.push_back(make_pair(i,j));

                    isfirst = false;

                }

                else if(board[i][j]=='x')

                    pi.push_back(make_pair(i-pi[].first,j-pi[].second));//存凸起相对于第一个的相对位置

            }

        }

        pi[].first = pi[].second = ;

        if(solve())

            printf("TAK\n");

        else

            printf("NIE\n");

    }

    return ;

}

巴特西

HYSBZ - 3750 Pieczęć（模拟）

最新文章

热门文章