#include <stdio.h>
#include <string.h>
const int N = 16;
const int SIZE = N*N*N*N;
int L[SIZE], R[SIZE], U[SIZE], D[SIZE], Sum[SIZE], Row[SIZE], Col[SIZE];
int lenx, id, deep, anslen;
bool OK;
int n, m, n1, m1;
int ini[N][N];
inline int read() {
char ch;
while( ch = getchar(), ch == ' ' || ch == '\n');
int d = ch - '0';
while( ch = getchar(), ch <= '9' && ch >= '0' ) d = d* 10 + ch - '0';
return d;
}
void pre(int cntcol) {
for(int i = 0; i <= cntcol; i ++) {
L[i] = i - 1;
R[i] = i + 1;
U[i] = D[i] = i;
Sum[i] = 0;
}
L[0] = cntcol; R[cntcol] = 0;
id = cntcol + 1;
}
void init() {
int cnt = 1;
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++) {
ini[i][j] = read();
if( ini[i][j] == 1 ) ini[i][j] = cnt ++;
}
}
n1 = read(); m1 = read();
pre(cnt-1);
}
inline void insert(int i, int *xx) {
for(int j = 0; j < lenx; j ++, id ++) {
int x = xx[j];
Row[id] = i;
Col[id] = x;
Sum[x] ++;
U[id] = x;
D[id] = D[x];
U[D[x]] = id;
D[x] = id;
if( j == 0 ) {
L[id] = R[id] = id;
} else {
L[id] = id - 1;
R[id] = id - j;
R[id-1] = id;
L[id-j] = id;
}
}
}
void build() {
int r = 0;
int x[N*N];
for(int i = 0; i <= n - n1; i ++ ) {
for(int j = 0; j <= m - m1; j ++) {
r ++;
lenx = 0;
for(int p = 0; p < n1; p ++) {
for(int q = 0; q < m1; q ++ ) {
if( ini[i+p][j+q] > 0 ) {
x[lenx++] = ini[i+p][j+q];
}
}
}
insert(r, x);
}
}
}
void remove(int &c) {
for(int i = D[c]; i != c ; i = D[i]) {
L[R[i]] = L[i];
R[L[i]] = R[i];
}
}
void resume(int &c) {
for(int i = U[c]; i != c ; i = U[i]) {
L[R[i]] = i;
R[L[i]] = i;
}
}
inline int Astar() {
int res = 0;
bool vis[N*N] = {false};
for(int i = R[0]; i != 0; i =R[i]) {
if( !vis[ i ] ) {
vis[ i ] = true;
res ++;
for(int j = D[i]; j != i; j = D[j]) {
for(int k = R[j]; k != j; k = R[k]) {
vis[ Col[k] ] = true;
}
}
}
}
return res;
}
void dfs(int dep) {
if( Astar() + dep > deep ) return ;
if(R[0] == 0) {
anslen = dep;
OK = true;
return;
}
int idx = R[0];
for(int i = R[0] ; i != 0 ; i = R[i]) {
if(Sum[i] < Sum[idx]) {
idx = i;
if( Sum[idx] <= 1 ) break;
}
}
for(int i = D[idx] ; i != idx; i = D[i]) {
remove(i);
for(int j = R[i] ; j != i ; j = R[j]) remove(j);
dfs( dep + 1 );
for(int j = L[i] ; j != i ; j = L[j]) resume(j);
resume(i);
if( OK ) return;
}
}
int main() {
while( scanf("%d %d", &n, &m) != EOF ) {
init();
build();
deep = 0;
anslen = 0;
OK = false;
while( !OK ) {
//deep ++;
dfs(0);
deep ++;
}
printf("%d\n", anslen);
}
//while(1);
return 0;
}
寫(xiě)了個(gè)可以用作板子的DLX非精確覆蓋