Skip to content

14028: 【原4028】久子的图章

题目

题目描述

author: Evensgn 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4028

题目描述

久子寄来了一幅画。

你却忽然想起那个初夏的傍晚,她将一枚木质图章放在你的手中,那是两年以前的事。

久子的画是一张 m * n 的方格纸,纸上有些格子被印上了黑色,其余的格子则保留了方格纸原有的白色。

那枚木质图章呢?它由 p * q 的方格组成,其中有些格子是凸起的,这些格子会沾上墨水。

能否用这个图章在纸上印出久子的画呢,你这样想着。

你自然知道,久子的图章在使用时,有如下的几点要求:

  • 图章不可以旋转
  • 不能把墨水印到纸外
  • 纸上的任一个格子最多只能被墨水印一次

如果能够用图章在纸上印出久子的画,请输出"Yes",否则请输出"No"(不包含引号)。

输入格式

第一行为一个整数T,表示测试数据的组数。

接下来T组测试数据,每组测试数据中:

  • 第一行为4个整数 m, n, p, q。
  • 接下来m行,每行n个数字(为0或1),描述久子的画。0表示留白的格子,1表示印上黑色的格子。
  • 接下来p行,每行q个数字(为0或1),描述图章。0表示不沾墨水的格子,1表示凸起的(沾墨水的)格子。

输出格式

对于每组测试数据,输出"Yes"或"No"。

样例输入

2
3 4 4 2
1 1 0 0
0 1 1 0
1 1 0 0
1 0
0 1
1 0
0 0
2 2 2 2
1 1
1 1
0 1
1 0

样例输出

Yes
No

数据规模

  • 对于40%的数据,图章上所有的格子都是凸起的。
  • 对于80%的数据,1 <= m,n,p,q <= 50。
  • 对于100%的数据,1 <= m,n,p,q <= 1000, 1 <= T <= 10。

FineArtz's solution

/* 久子的图章 */
#include <iostream>
#include <cstdio>
using namespace std;

class Point{
public:
    Point() : x(0), y(0) {}
    Point(int xx, int yy) : x(xx), y(yy) {};
    int x, y;
};

bool gra[1005][1005] = {0};
Point pic[1000000];

void solve(){
    int m, n, p, q;
    int cntg = 0;
    cin >> m >> n >> p >> q;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j){
            scanf("%d", &gra[i][j]);
            if (gra[i][j]) ++cntg;
        }
    int t = 0, cntp = 0;
    for (int i = 1; i <= p; ++i)
        for (int j = 1; j <= q; ++j){
            scanf("%d", &t);
            if (t == 1){
                ++cntp;
                pic[cntp].x = i;
                pic[cntp].y = j;
            }
        }
    /*if (cntg % cntp != 0){
        cout << "No" << endl;
        return;
    }
    if (m > 50 && n > 50){
        cout << "No" << endl;
        return;
    }*/
    for (int i = 1; i <= m; ++i){
        for (int j = 1; j <= n; ++j){
            if (gra[i][j]){
                for (int l = 2; l <= cntp; ++l){
                    int nx = i + pic[l].x - pic[1].x, ny = j + pic[l].y - pic[1].y;
                    if (nx <= 0 || ny <= 0 || nx > m || ny > n){
                        printf("No\n");
                        return;
                    }
                    if (gra[nx][ny]) gra[nx][ny] = 0;
                    else{
                        printf("No\n");
                        return;
                    }
                }
            }
        }
    }
    printf("Yes\n");
}

int main(){
    int t;
    cin >> t;
    for (int i = 0; i != t; ++i)
        solve();
    return 0;
}

ligongzzz's solution

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

bool a[1009][1009] = { 0 };
int b[1000009][2] = { 0 };
int b_num = 0;
int a_num[1009] = { 0 };

int main() {
    int T;
    cin >> T;

    for (; T > 0; ) {
        int m, n, p, q;
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        memset(a_num, 0, sizeof(a_num));
        b_num = 0;
        scanf("%d %d %d %d", &m, &n, &p, &q);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j) {
                scanf("%d", &a[i][j]);
                if (a[i][j])
                    a_num[i]++;
            }
        for (int i = 0; i < p; ++i)
            for (int j = 0; j < q; ++j) {
                int temp;
                scanf("%d", &temp);
                if (temp) {
                    b[b_num][0] = i;
                    b[b_num++][1] = j;
                }
            }
        //开始比较
        for (int i = 0; i <= m; ++i) {
            for (int j = 0; j <= n; ++j) {
                //判断位置是否匹配
                if (a[i][j]) {
                    //循环
                    for (int k = 0; k < b_num; ++k) {
                        int bx = b[k][0] - b[0][0] + i, by = b[k][1] - b[0][1] + j;
                        if (bx < m && by < n && bx >= 0 && by >= 0 && a[bx][by]) {
                            a[bx][by] = false;
                            --a_num[bx];
                        }
                        else {
                            printf("No\n");
                            goto start;
                        }
                    }
                }
            }
            if (a_num[i] > 0) {
                printf("No\n");
                goto start;
            }
        }
        //检查
        for(int i=0;i<m;++i)
            if (a_num[i] > 0) {
                printf("No\n");
                goto start;
            }
        printf("Yes\n");
    start:
        --T;
    }

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstdio>
#include <climits>
using namespace std;

int run() {
    int m, n, p, q;
    int S[1000][1000];
    int G[1000][1000];
    scanf("%d%d%d%d", &m, &n, &p, &q);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &G[i][j]);
        }
    }
    int x2 = INT_MIN, x1 = INT_MAX, y2 = INT_MIN, y1 = INT_MAX;
    bool f = false;
    for (int i = 0; i < p; i++) {
        for (int j = 0; j < q; j++) {
            scanf("%d", &S[i][j]);
            if (S[i][j] == 1) {
                f = true;
                x1 = min(x1, i);
                x2 = max(x2, i);
                y1 = min(y1, j);
                y2 = max(y2, j);
            }
        }
    }
    if (!f) {
        return false;
    }
    int pin_x = 0, pin_y = 0;
    bool pin = false;
    for (int i = 0; i < p; i++) {
        for (int j = 0; j < q; j++) {
            S[i][j] = S[i + x1][j + y1];
            if (!pin) {
                if (S[i][j] == 1) {
                    pin = true;
                    pin_x = i;
                    pin_y = j;
                }
            }
        }
    }
    p = x2 - x1 + 1;
    q = y2 - y1 + 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (G[i][j] == 1) {
                for (int a = 0; a < p; a++) {
                    for (int b = 0; b < q; b++) {
                        if (S[a][b] == 1) {
                            int s_x = i + a - pin_x;
                            int s_y = j + b - pin_y;
                            if (s_x < 0 || s_y < 0 || s_x >= m || s_y >= n) return false;
                            if (G[s_x][s_y] == 1) {
                                G[s_x][s_y] = 0;
                            } else {
                                return false;
                            }
                        }
                    }
                }
            }
        }
    }
    return true;
}
int main() {
    int T;
    scanf("%d", &T);
    for (int i = 0; i < T; i++) 
    if(run())
        printf("Yes\n");
    else printf("No\n");
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
int rmargin,lmargin,dmargin,m,n,p,q,t,x,sx,sy,patx[1000001],paty[1000001],map[1001][1001],num,pnum;
bool flag;
int main() {
    scanf("%d",&t);
    for (int i=0;i<t;++i){
        flag=true;
        num=0;
        lmargin=0;
        rmargin=0;
        dmargin=0;
        pnum=0;
        scanf("%d%d%d%d",&m,&n,&p,&q);
        for (int j=0;j<m;++j)
            for (int k=0;k<n;++k) {
                scanf("%d", &map[j][k]);
                if (map[j][k]) pnum++;
            }
        for (int j=0;j<p;++j)
            for (int k=0;k<q;++k)
            {
               scanf("%d",&x);
               if (x){
                   if (num==0) {
                       sx=j;
                       sy=k;
                       num++;
                   }
                   else{
                       patx[num]=j-sx;
                       paty[num]=k-sy;
                       if (paty[num]<0)
                           lmargin=max(lmargin,paty[num]);
                       rmargin=max(rmargin,paty[num]);
                       dmargin=max(dmargin,patx[num]);
                       num++;
                   }
               }
            }
        for (int j=0;j<m-dmargin;++j){
            for (int k=lmargin;k<n-rmargin;++k)
                if (map[j][k]){
                    map[j][k]=0;
                    for (int l=1;l<num;++l)
                        if (!map[j+patx[l]][k+paty[l]]) {
                            flag = false;
                            break;
                        }
                        else
                            map[j+patx[l]][k+paty[l]]=0;
                    if (!flag) break;
                    pnum-=num;
                    if (!pnum) break;
                }
            if (!flag) break;
            if (!pnum) break;
        }
        if (!flag) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}