解题思路

首先将所有有怪物的坐标编号，作为 DLX 矩阵的列，然后将所有攻击区域以选定的某个顶点坐标编号，作为 DLX 矩阵的行。这样本题就转化成了求最少的行数（即攻击次数）使得所有列（即怪物）都被覆盖，而且由于题目允许同一个位置被多次攻击到，这里我们使用 DLX 的重复覆盖算法来解决这个问题。

参考代码

#include <cstdio>
#include <cstring>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 15*15;
const int MAXM = 15*15;

struct DLX {
    int l, r, u, d;
    int row, col;
} dlx[(MAXN+1)*(MAXM+1)+MAXM+1];

int sz[MAXM+1], idx, head[MAXN+1], ans;
bool del[MAXM+1];

void Init(int n, int m) {
    for(int i=0; i<=m; ++i) {
        dlx[i].u = dlx[i].d = i;
        dlx[i+1].l = i;
        dlx[i].r = i+1;
        sz[i] = 0;
    }
    dlx[m].r = 0;
    dlx[0].l = m;
    idx = m+1;
    for(int i=1; i<=n; ++i) {
        head[i] = -1;
    }
}

void Insert(int r, int c) {
    sz[c]++;
    // U/D
    dlx[dlx[c].u].d = idx;
    dlx[idx].u = dlx[c].u;
    dlx[idx].d = c;
    dlx[c].u = idx;
    dlx[idx].row = r;
    dlx[idx].col = c;
    // L/R
    if(head[r] == -1)
        head[r] = dlx[idx].l = dlx[idx].r = idx;
    else {
        dlx[dlx[head[r]].l].r = idx;
        dlx[idx].l = dlx[head[r]].l;
        dlx[idx].r = head[r];
        dlx[head[r]].l = idx;
    }
    idx++;
}

void Remove(int c) {
    for(int i=dlx[c].d; i!=c; i=dlx[i].d) {
        dlx[dlx[i].r].l = dlx[i].l;
        dlx[dlx[i].l].r = dlx[i].r;
    }
}

void Resume(int c) {
    for(int i=dlx[c].u; i!=c; i=dlx[i].u) {
        dlx[dlx[i].r].l = dlx[dlx[i].l].r = i;
    }
}

int A() {
    memset(del, false, sizeof del);
    int ret = 0;
    for(int i=dlx[0].r; i; i=dlx[i].r) {
        if(!del[i]) {
            ret++;
            del[i] = true;
            for(int j=dlx[i].d; j!=i; j=dlx[j].d) {
                for(int k=dlx[j].r; k!=j; k=dlx[k].r) {
                    del[dlx[k].col] = true;
                }
            }
        }
    }

    return ret;
}

void Dance(int cnt) {
    if(cnt+A() >= ans) return;
    if(dlx[0].r == 0) {
        ans = cnt;
        return;
    }
    else {
        int minsz = INF, c;
        for(int i=dlx[0].r; i!=0; i=dlx[i].r) {
            if(sz[i] == 0) return;
            if(sz[i] < minsz) {
                minsz = sz[i];
                c = i;
                if(minsz == 1) break;
            }
        }
        for(int i=dlx[c].d; i!=c; i=dlx[i].d) {
            Remove(i);
            for(int j=dlx[i].r; j!=i; j=dlx[j].r) {
                Remove(j);
            }
            Dance(cnt+1);
            for(int j=dlx[i].l; j!=i; j=dlx[j].l) {
                Resume(j);
            }
            Resume(i);
        }
    }
}

int main(int argc, char const *argv[]) {
    int n, m, v, a[16][16], n1, m1;
    while(~ scanf("%d %d", &n, &m)) {
        int id = 0;
        for(int i=1; i<=n; ++i) {
            for(int j=1; j<=m; ++j) {
                scanf("%d", &v);
                if(v == 1) a[i][j] = ++id;
                else a[i][j] = 0;
            }
        }
        Init(n*m, id);
        scanf("%d %d", &n1, &m1);
        for(int i=1; i<=n-n1+1; ++i) {
            for(int j=1; j<=m-m1+1; ++j) {
                for(int k=i; k<=i+n1-1; ++k) {
                    for(int l=j; l<=j+m1-1; ++l) {
                        if(a[k][l]) Insert((i-1)*m+j, a[k][l]);
                    }
                }
            }
        }
        ans = INF;
        Dance(0);
        printf("%d\n", ans);
    }
    
    return 0;
}