Stamp Grid (USACO Bronze 2023 February)

给定一幅 $N\cdot N$ 的画，以及 $K\cdot K$ 的邮票，邮票可以任意90度整倍旋转，问是否可以用邮票覆盖画中所有有油墨的格子，且不覆盖没有油墨的格子。

注意到N和K都较小（20），那么我们考虑是否能暴力搜索解决问题，把所有邮票可能的位置和旋转全部试一遍，每次如果没有覆盖到没有油墨的格子，就把邮票印上去。因为有油墨的格子覆盖得越多越好，所以“能印则印”是合理的策略。如果所有的位置和旋转都试过之后，没有没有油墨的格子了，那么就是YES，否则就是NO。

复杂度是 $\mathcal{O}(N^4)$ ，满足小于 $10^8$ 的复杂度要求。

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int T,n,K;  // T<=100, n<=20
char p[25][25], P[25][25];
char s[25][25];
 
int rem;    // remaining cells
 
void stamp(int i, int j, int dir) { // dir is 0-3
    bool ok = true;
    for (int turn = 0; turn < 2; turn++) {  // turn 0 is for checking if stamp fits
        for (int k = 0; k < K; k++)
            for (int l = 0; l < K; l++) {
                int r = dir == 0 ? k :
                        dir == 1 ? K-1-l :
                        dir == 2 ? K-1-k : l;
                int c = dir == 0 ? l :
                        dir == 1 ? k :
                        dir == 2 ? K-1-l : K-1-k;
                if (s[r][c] == '*') {
                    if (p[i+k][j+l] == '.')
                        ok = false;
                    if (turn && P[i+k][j+l] == '*') {
                        P[i+k][j+l] = '.';
                        rem--;
                    }
                }                
            }
        if (!ok) break;
    }
}
 
int main() {
    scanf("%d", &T);
    for (int t = 0; t < T; t++) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%s", &p[i]);
        scanf("%d", &K);
        for (int i = 0; i < K; i++)
            scanf("%s", &s[i]);
        rem = 0;
        for (int i = 0; i < n; i++) {
            strcpy(P[i],p[i]);
            for (int j = 0; j < n; j++)
                if (p[i][j] =='*')
                    rem++;
        }
        for (int i = 0; i < n-K+1; i++)
            for (int j = 0; j < n-K+1; j++) {
                stamp(i,j,0);
                stamp(i,j,1);
                stamp(i,j,2);
                stamp(i,j,3);
            }
        printf("%s\n", rem == 0 ? "YES" : "NO");
    }
    return 0;
}