FZU 1686 神龍的難題

Description

這是個劍與魔法的世界.英雄和魔物同在,動蕩和安定并存.但總的來說,庫爾特王國是個安甯的國家,人民安居樂業,魔物也比較少.但是.總有一些魔物不時會進入城市附近,幹擾人民的生活.就要有一些人出來守護居民們不被魔物侵害.魔法使艾米莉就是這樣的一個人.她騎着她的坐騎,神龍米格拉一起消滅幹擾人類生存的魔物,維護王國的安定.艾米莉希望能夠在損傷最小的前提下完成任務.每次戰鬥前,她都用時間停止魔法停住時間,然後米格拉他就可以發出火球燒死敵人.米格拉想知道,他如何以最快的速度消滅敵人,減輕艾米莉的負擔.

Input

Output

Sample Input

4 4

1 0 0 1

0 1 1 0

0 1 1 0

1 0 0 1

2 2

4 4 

0 0 0 0

0 1 1 0

0 1 1 0

0 0 0 0

2 2

Sample Output

4

1

建圖，dlx重複覆寫

#include<cstdio>
#include<vector>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll maxn = 25;
int n, m, x, y, mp[maxn][maxn], t1, t2;

inline void read(int &ret)
{
  char c;
  do {
    c = getchar();
  } while (c < '0' || c > '9');
  ret = c - '0';
  while ((c = getchar()) >= '0' && c <= '9')
    ret = ret * 10 + (c - '0');
}

struct DLX
{
  #define maxn 10005
  #define F(i,A,s) for (int i=A[s];i!=s;i=A[i])
  int L[maxn], R[maxn], U[maxn], D[maxn];
  int row[maxn], col[maxn], ans[maxn], cnt[maxn];
  int n, m, num, sz;

  void add(int now, int l, int r, int u, int d, int x, int y)
  {
    L[now] = l; R[now] = r; U[now] = u;
    D[now] = d;   row[now] = x;  col[now] = y;
  }
  void reset(int n, int m, int x)
  {
    if (x) num = 0x7FFFFFFF; else num = 0;
    this->n = n; this->m = m;
    for (int i = 0; i <= m; i++)
    {
      add(i, i - 1, i + 1, i, i, 0, i);
      cnt[i] = 0;
    }
    L[0] = m;   R[m] = 0;   sz = m + 1;
  }
  void insert(int x, int y)
  {
    int ft = sz - 1;
    if (row[ft] != x)
    {
      add(sz, sz, sz, U[y], y, x, y);
      U[D[sz]] = sz; D[U[sz]] = sz;
    }
    else
    {
      add(sz, ft, R[ft], U[y], y, x, y);
      R[L[sz]] = sz; L[R[sz]] = sz;
      U[D[sz]] = sz; D[U[sz]] = sz;
    }
    ++cnt[y]; ++sz;
  }

  //精确覆寫
  void remove(int now)
  {
    R[L[now]] = R[now];
    L[R[now]] = L[now];
    F(i, D, now) F(j, R, i)
    {
      D[U[j]] = D[j];
      U[D[j]] = U[j];
      --cnt[col[j]];
    }
  }
  void resume(int now)
  {
    F(i, U, now)  F(j, L, i)
    {
      D[U[j]] = j;
      U[D[j]] = j;
      ++cnt[col[j]];
    }
    R[L[now]] = now;
    L[R[now]] = now;
  }
  int dfs(int x)
  {
    if (!R[0]) return 1;
    int now = R[0];
    F(i, R, 0) if (cnt[now]>cnt[i]) now = i;
    remove(now);
    F(i, D, now)
    {
      ans[x] = row[i];
      F(j, R, i) remove(col[j]);
      if (dfs(x + 1)) return 1;
      F(j, L, i) resume(col[j]);
    }
    resume(now);
    return 0;
  }
  //精确覆寫

  //重複覆寫
  void Remove(int now)
  {
    F(i, D, now)
    {
      L[R[i]] = L[i];
      R[L[i]] = R[i];
    }
  }
  void Resume(int now)
  {
    F(i, U, now) L[R[i]] = R[L[i]] = i;
  }
  int vis[maxn];
  int flag[maxn];
  int A()
  {
    int dis = 0;
    F(i, R, 0) vis[i] = 0;
    F(i, R, 0) if (!vis[i])
    {
      dis++;  vis[i] = 1;
      F(j, D, i) F(k, R, j) vis[col[k]] = 1;
    }
    return dis;
  }
  void Dfs(int x)
  {
    if (!R[0]) num = min(num, x);
    else if (x + A()<num)
    {
      int now = R[0];
      F(i, R, 0) if (cnt[now]>cnt[i]) now = i;
      F(i, D, now)
      {
        Remove(i); F(j, R, i) Remove(j);
        Dfs(x + 1);
        F(j, L, i) Resume(j); Resume(i);
      }
    }
  }
  //重複覆寫
}dlx;

int main()
{
  //read(T);
  while (scanf("%d%d", &n, &m) == 2)
  {
    t1 = t2 = 0;
    for (int i = 1; i <= n; ++i)
      for (int j = 1; j <= m; ++j)
      { 
        scanf("%d", &mp[i][j]); 
        t2 += mp[i][j];
        if (mp[i][j]) mp[i][j] = t2;
      }
    scanf("%d%d", &x, &y);
    t1 = (n - x + 1)*(m - y + 1);
    dlx.reset(t1, t2, 1);
    t1 = 0;
    for (int i = 1; i + x - 1 <= n; i++)
      for (int j = 1; j + y - 1 <= m; j++)
      {
        t1++;
        for (int x1 = 0; x1 < x; x1++)
          for (int y1 = 0; y1 < y; y1++)
            if (mp[i + x1][j + y1]) dlx.insert(t1, mp[i + x1][j + y1]);
      }
    dlx.Dfs(0);
    printf("%d\n", dlx.num);
  }
  return 0;
}