Morris' Blog

2011-08-09 08:41:48Morris

a209. 街友的寒冷夜晚

留言 0 收藏 0 推薦 0

a209. 街友的寒冷夜晚
內容：

這已經是古賀離家出走的第四天了

每到夜晚就得忍受街頭 10 度的低溫入眠

古賀再也忍不住這種溫度而去垃圾桶找了幾張破報紙充當棉被

先是草草的抓了幾張大的蓋住身體

但報紙實在是太破碎了

胡亂遮住身體之後還是有冷風從沒蓋住的地方灌入

古賀想請你算出如何用最少的小塊報紙把風灌入的地方蓋起來 (報紙可以互相重疊)

因為他實在是太冷又太累了

具體來說，現在有一個 n*m 的 01 矩陣，如果某個位置是 1，則代表它要被覆蓋，否則不能被覆蓋。請你用最少個數的正方形覆蓋所有的 1，可以重複覆蓋。

輸入說明：

每組數據的第一行為正整數 m, n

接下來為一個 n*m 的 01 矩陣

以 0 0 作為結尾

輸出說明：

每組數據輸出最少正方形個數

範例輸入：

4 3
0 1 1 1
1 1 1 1
1 1 1 1
8 5
0 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 0 1 1 1 1
0 1 1 1 0 1 1 1
0 0

範例輸出：

2
6

提示：

× 感謝 example 編輯題目內容

× (`д´)っ゛早知道, 如果是悲劇的話, 題目人名應該要用「小光」

出處：

重複覆蓋問題 (管理：morris1028)

作法 : Dancing Links
只需要將以某格為左上角的最大正方形放入即可,
再來藉由Greedy, 若有某個正方形, 被另外一個正方形覆蓋,
也是可以替除的部分, 為了加速 Dancing Links, 我們將把多餘的列替除,
並且將每個設定的列重新編號, 打到 1~x, 一對一的

/**********************************************************************************/
/* Problem: a209 "街友的寒冷夜晚" from 重複覆蓋問題                 */
/* Language: C                                                                   */
/* Result: AC (400ms, 288KB) on ZeroJudge                                        */
/* Author: morris1028 at 2011-08-09 07:16:52                                     */
/**********************************************************************************/

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Maxv 100000
struct DacingLinks {
   int left, right;
   int up, down;
   int data, ch, rh;
}DL[401*400 + 401];
int s[401], o[8001], head, size, Ans;
struct Data {
   int l, a, b;
}Data[8000];
void Remove(int c) {
   static int i;
   for(i = DL[c].down; i != c; i = DL[i].down) {
       DL[DL[i].right].left = DL[i].left;
       DL[DL[i].left].right = DL[i].right;
       s[DL[i].ch]--;
   }
}
void Resume(int c) {
   static int i;
   for(i = DL[c].down; i != c; i = DL[i].down) {
       DL[DL[i].right].left = i;
       DL[DL[i].left].right = i;
       s[DL[i].ch]++;
   }
}
int used[401] = {};
int H() {
   static int c, ret, i, j, time = 0;
   for(c = DL[head].right, ++time, ret = 0; c != head; c = DL[c].right) {
       if(used[c] != time) {
           ret ++, used[c] = time;
           for(i = DL[c].down; i != c; i = DL[i].down)
               for(j = DL[i].right; j != i; j = DL[j].right)
                   used[DL[j].ch] = time;
       }
   }
   return ret;
}
void DFS(int k) {
   if(k + H() >= Ans)   return;
   if(DL[head].right == head) {
       if(k < Ans)   Ans = k;
       return;
   }
   int t = Maxv, c, i, j;
   for(i = DL[head].right; i != head; i = DL[i].right) {
       if(s[i] < t) {
           t = s[i], c = i;
       }
   }
   for(i = DL[c].down; i != c; i = DL[i].down) {
       Remove(i);
       for(j = DL[i].right; j != i; j = DL[j].right)   Remove(j);
       DFS(k+1);
       for(j = DL[i].left; j != i; j = DL[j].left)       Resume(j);
       Resume(i);
   }
}
int new_node(int up, int down, int left, int right) {
   DL[size].up = up, DL[size].down = down;
   DL[size].left = left, DL[size].right = right;
   DL[up].down = DL[down].up = DL[left].right = DL[right].left = size;
   return size++;
}
void new_row(int n, int Row[]) {
   int a, r, row = -1, k;
   for(a = 0; a < n; a++) {
       r = Row[a];
       DL[size].ch = r, s[r]++;
       if(row == -1) {
           row = new_node(DL[DL[r].ch].up, DL[r].ch, size, size);
           DL[row].rh = a;
       }else {
           k = new_node(DL[DL[r].ch].up, DL[r].ch, DL[row].left, row);
           DL[k].rh = a;
       }
   }
}
void init(int m) {
   size = 0;
   head = new_node(0, 0, 0, 0);
   int i;
   for(i = 1; i <= m; i++) {
       new_node(i, i, DL[head].left, head);
       DL[i].ch = i, s[i] = 0;
   }
}
int min(int x, int y) {
   return x < y ? x : y;
}
int max(int x, int y) {
   return x > y ? x : y;
}
void QuickSort(int , int );
main() {
   int m, n, a, b, c, d, e, x;
   while(scanf("%d %d", &m, &n) == 2) {
       if(n == 0 && m == 0) break;
       int map[21][21] = {};
       for(a = 1; a <= n; a++)
           for(b = 1; b <= m; b++)
               scanf("%d", &map[a][b]);
       int DP[21][21] = {}, Row[401], t = 0, rr = 0;
       int Cut[21][21] = {}, tag[21][21] = {}, Yestag = 0;
       for(a = 1; a <= n; a++) {
           for(b = 1; b <= m; b++) {
               if(map[a][b]) {
                   DP[a][b] = DP[a-1][b-1];
                   DP[a][b] = DP[a][b] < DP[a][b-1] ? DP[a][b] : DP[a][b-1];
                   DP[a][b] = DP[a][b] < DP[a-1][b] ? DP[a][b] : DP[a-1][b];
                   DP[a][b]++;
                   for(c = a-DP[a][b]+1; c <= a; c++)
                       for(d = b-DP[a][b]+1; d <= b; d++) {
                           if(c == a && d == b) continue;
                           x = min(c -(a-DP[a][b]+1)+1, d-(b-DP[a][b]+1)+1);
                           Cut[c][d] = max(Cut[c][d], x);
                       }
                   Yestag ++, tag[a][b] = Yestag;
               }
           }
       }
       for(a = 1; a <= n; a++) {
           for(b = 1; b <= m; b++) {
               if(map[a][b] && DP[a][b] > Cut[a][b]) {
                   Data[rr].l = DP[a][b], Data[rr].a = a, Data[rr].b = b, rr++;
               }
           }
       }
       init(Yestag), QuickSort(0, rr-1);
       for(a = 0; a < rr; a++) {
           e = Data[a].l, t = 0;
           for(c = Data[a].a-e+1; c <= Data[a].a; c++)
               for(d = Data[a].b-e+1; d <= Data[a].b; d++)
                   if(tag[c][d])
                       Row[t++] = tag[c][d];
           new_row(t, Row);
       }
       Ans = Maxv,   DFS(0);
       printf("%d\n", Ans);
   }
   return 0;
}
void Swap(int x, int y) {
    int t;
    t = Data[x].l, Data[x].l = Data[y].l, Data[y].l = t;
   t = Data[x].a, Data[x].a = Data[y].a, Data[y].a = t;
   t = Data[x].b, Data[x].b = Data[y].b, Data[y].b = t;
}
int split(int l, int r) {
    int a = l, b, t = Data[l].l;
    for(b = l+1; b <= r; b++) {
        if(Data[b].l >= t)
            a++, Swap(a, b);
    }
    Swap(l, a);
    return a;
}
void QuickSort(int l, int r) {
    if(l < r) {
        int v = l + rand()%(r-l);
        Swap(l, v);
        int m = split(l, r);
        QuickSort(l, m-1);
        QuickSort(m+1, r);
    }
}

上一篇：d705. 判断质数（二）

下一篇：d522. 走棋盘

Morris' Blog

a209. 街友的寒冷夜晚

你可能感興趣的文章

【三重美食-車路頭-原汁牛肉麵】(華哥哥美食報報)

實踐第26天

一隻就好

2024.11.25

最後第51天