Pieczęć

admin管理员组

文章数量:1531767

一张n*m的方格纸，有些格子需要印成黑色，剩下的格子需要保留白色。
你有一个a*b的印章，有些格子是凸起（会沾上墨水）的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求：
（1）印章不可以旋转。
（2）不能把墨水印到纸外面。
（3）纸上的同一个格子不可以印多次。

 

第一行一个整数q(1<=q<=10)，表示测试点数量。
接下来q个测试点，每个测试点中：
第一行包含4个整数n,m,a,b(1<=n,m,a,b<=1000)。
接下来n行，每行m个字符，描述纸上的图案。'.'表示留白，'x'表示需要染黑。
接下来a行，每行b个字符，描述印章。'.'表示不沾墨水，'x'表示沾墨水。

对于每个测试点，输出TAK（是）或NIE（否）。

题解：

用vector存pair（坐标）的方式存印章，然后暴力所有点，对于遇到的第一个黑点判断是否满足题意

1越界不满足

2与印章不匹配

1°印章上有x，图上没有（直接在ck函数里判断即可）

2°图上有x，印章上没有x（统计黑点总数，看最后刷的黑点数是否等于总数）

 

Ac代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int maxn = 1e3+20;
int t,n,m,a,b,cnt;
char mmp[maxn][maxn],s[maxn];
bool vis[maxn][maxn];
vector<pll> brush;
bool ck(int x,int y){
    for(auto i:brush){
        if(x+i.first>n||y+i.second>m||x+i.first<1||y+i.second<1)
            return false;
        if(mmp[x+i.first][y+i.second]!='x')
            return false;
        vis[x+i.first][y+i.second] = 1,cnt--;
    }
    return true;
}
void sovle(){
    memset(vis,0,sizeof(vis));
    cnt = 0,brush.clear();
    cin>>n>>m>>a>>b;
    for(int i=1;i<=n;i++){
        cin>>mmp[i]+1;
        for(int j=1;mmp[i][j];j++)
            if(mmp[i][j]=='x')
                cnt++;
    }
    pll Anchor = {0,0};///锚定点,即第一个点,用于定位印章剩余点
    for(int i=1;i<=a;i++){
        cin>>s+1;
        for(int j=1;s[j];j++)
            if(s[j]=='x')
                if(!Anchor.first && !Anchor.second)
                    brush.push_back(Anchor),Anchor = {i,j};
                else
                    brush.push_back(make_pair(i-Anchor.first,j-Anchor.second));
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(mmp[i][j]=='x' && !vis[i][j] && !ck(i,j)){
                cout<<"NIE"<<endl;
                return;
            }
        }
    }
    cout<<(!cnt?"TAK":"NIE")<<endl;
}
int main(){
    cin>>t;
    while(t--)
        sovle();
    return 0;
}

本文标签： Piecz