题解 P3585 【[POI2015]PIE】

Link_Space · 2021-01-31 15:37:26 · 题解

一道比较水的模拟题，思路很好想，代码也很好写，码量并不大。

具体思路如下：遍历印章，找到印章中的第一个x并以这个x为参考系，将其他x与这个x的相对坐标存到一个数组之中。接下来就遍历需要印出的图案，每遇到一个x就立马以这个x为参考系，看看能否和印章吻合，如果不能的话立马跳出，说明这个图案永远无法由这个印章构成，如果能的话就将与印章吻合的所有x都变为.，然后继续比对，直至所有x都被印章吻合之后，说明这个图案可以被该印章构成。

以下是代码（略显繁琐，可以精简）

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1e3 + 5;
const int M = 1e6 + 5;
char Map[N][N];
char Stamp[N][N];
int stax;
int stay;
struct Node{
    int x;
    int y;
}relative[M];
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        memset(relative, 0, sizeof relative);
        int n, m;
        scanf("%d%d", &n, &m);
        int a, b;
        scanf("%d%d", &a, &b);
        for (int i = 1; i <= n;i++)
            for (int j = 1; j <= m;j++)
                cin >> Map[i][j];
        bool flag = false;
        int cnt = 0;
        for (int i = 1; i <= a;i++)
        {
            for (int j = 1; j <= b;j++)
            {
                cin >> Stamp[i][j];
                if(Stamp[i][j]=='x')
                {
                    if(!flag)
                        stax = i, stay = j;
                    else
                        relative[++cnt].x = i - stax, relative[cnt].y = j - stay;
                    flag = true;
                }
            }
        }
        bool can = true;
        for (int i = 1; i <= n;i++)
        {
            for (int j = 1; j <= m;j++)
            {
                if (Map[i][j] == 'x')
                {
                    for (int k = 1; k <= cnt;k++)
                    {
                        int xx = i + relative[k].x;
                        int yy = j + relative[k].y;
                        if(xx<1||xx>n||yy<1||yy>m)
                        {
                            can = false;
                            break;
                        }
                        if(Map[xx][yy]!='x')
                        {
                            can = false;
                            break;
                        }
                    }
                    if(can)
                    {
                        for (int k = 1; k <= cnt;k++)
                        {
                            int xx = i + relative[k].x;
                            int yy = j + relative[k].y;
                            Map[xx][yy] = '.';
                        }
                    }
                }
                if(!can)
                    break;
            }
            if(!can)
                    break;
        }
        if(!can)
            puts("NIE");
        else
            puts("TAK");
    }
    return 0;
}