poj 1038 Bugs Integrated, Inc.

Bugs Integrated, Inc.

Description

Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 2*3 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into N*M unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.

Finally, the plate of silicon is cut into memory chips. Each chip consists of 2*3 (or 3*2) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.
Task
You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.

Input

The first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).

Output

For each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.

Sample Input

2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4

Sample Output

3
4

Bugs Integrated, Inc.

描述

Bugs Integrated, Inc. 是高级存储芯片的主要制造商。他们正在开始生产新的 6 TB Q-RAM 芯片。每个筹码由以 2*3 矩形排列的六个单位正方形组成。Q-RAM 芯片的制造方式是将一块矩形硅片分成 N*M 个单位正方形。然后仔细测试所有方块，坏的用黑色记号笔标记。

最后，将硅片切割成存储芯片。每个筹码由 2*3（或 3*2）个单位方块组成。当然，任何筹码都不能包含任何坏的（标记的）方块。可能无法切割板以使每个好的单位方块都是某个内存芯片的一部分。该公司希望尽可能少地浪费好方块。因此，他们想知道如何切割板材以使切屑数量尽可能多。
任务
你得到几个硅板的尺寸和每个板的所有坏单元方块的列表。您的任务是编写一个程序，为每个板计算可以从板上切下的最大芯片数。

输入

输入文件的第一行由一个整数 D (1 <= D <= 5) 组成，表示硅板的数量。接下来是 D 个块，每个块描述一个硅板。每个块的第一行包含三个整数 N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) 由单个空格分隔。N 是板的长度，M 是它的高度，K 是板中坏方块的数量。以下 K 行包含一个坏方块列表。每行由两个整数 x 和 y 组成 (1 <= x <= N, 1 <= y <= M) ?一个坏方块的坐标（左上角的方块坐标为 [1, 1]，右下角为 [ N，M]）。

输出

对于输入文件中的每个板，输出一行，其中包含可以从板中切出的最大内存芯片数。

样本输入

2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4

样本输出

3
4

代码：

#include 
#include 
#include 
#include 
using namespace std;

int n,m,k,x,y,ans,o;
int three[15],q[15],p[15],map[160][15],f[2][60000];

void pre(){
   three[0] = 1;
   for (int i = 1;i <= 11;i ++) three[i] = three[i - 1] * 3;
}

int update(int* p,int* q,int i,int j){
   int cnt = 0,res = 0;
   memset(q,0,sizeof q);
   memset(p,0,sizeof p);
   for (int k = 1;k <= m;k ++){
       p[k] = j % 3;
       j /= 3;
   }
   for (int k = 0;k < m;k ++){
       if (map[i][k + 1]) q[k + 1] = 2,res += three[k] * 2;
       else if (p[k + 1] == 2) q[k + 1] = 1,res += three[k];
       else if (p[k + 1] < 2) q[k + 1] = 0;
   }
   return res;
}

void dfs(int now,int y,int r){
   if (now > ans) ans = now;
   if (y + 1 <= m && p[y] == 0 && p[y + 1] == 0 && q[y] == 0 && q[y + 1] == 0){
       q[y] = 2;
       q[y + 1] = 2;
       int i = r + three[y - 1] * 2 + three[y] * 2;
       if (now + 1 > f[o][i]) f[o][i] = now + 1;
       dfs(now + 1,y + 2,i);
       q[y] = 0;
       q[y + 1] = 0;
   }
   if (y + 2 <= m && q[y] == 0 && q[y + 1] == 0 && q[y + 2] == 0){
       q[y] = q[y + 1] = q[y + 2] = 2;
       int i = r + three[y - 1] * 2 + three[y] * 2 + three[y + 1] * 2;
       if (now + 1 > f[o][i]) f[o][i] = now + 1;
       dfs(now + 1,y + 3,i);
       q[y] = q[y + 1] = q[y + 2] = 0;
   }
   if (now > f[o][r]) f[o][r] = now;
   if (y + 1 <= m) dfs(now,y + 1,r);
}

int main(){

   int T;
   cin >> T;
   pre();
   while (T --){
       scanf("%d%d%d",&n,&m,&k);
       memset(map,0,sizeof map);
       for (int i = 1;i <= k;i ++){
           scanf("%d%d",&x,&y);
           map[x][y] = 1;
       }

       x = 0;
       for (int i = 1;i <= m;i ++){
           if (map[1][i]) x += 2 * three[i - 1];else x += three[i - 1];
       }

       o = 0;
       memset(f,-1,sizeof f);
       f[o][x] = 0;
       ans = 0;
       for (int i = 2;i <= n;i ++){
           o = 1 - o;
           memset(f[o],-1,sizeof f[o]);
           for (int j = 0;j < three[m];j ++) if (f[1 - o][j] != -1){
               int r = update(p,q,i,j);
               dfs(f[1 - o][j],1,r);
           }
       }
       cout << ans << endl;
   }

   return 0;
}