zju1516参考答案

   1 /*
   2 zoj 1516 DFS
   3 ymc 2008/09/13
   4 题目大意：
   5 n*m的地图上，有k个黑的单元格。两个连续的白色格子(1×2或者2×1)称为有效的。
   6 求最多有能得到多少个有效的格子。
   7 分析与解题思路：
   8 超出地图边界的一圈全部设为黑色(这样不用考虑越界)。
   9 有效的格子不是横着的就是竖着的。所有孤立的白色单元格是无效的。直接设置为黑色。
  10 对每一个白色的单元格，可能有三种情况：
  11 1）成为有效格子的左边一个
  12 2）成为有效格子的上边一个
  13 3）不在任何有效格子中
  14 注意：右边和下边的情况不用考虑，因为上边和左边对应的另外一个格子就是。
  15 用DFS搜索
  16 */
  17 #include <iostream>
  18 using namespace std;
  19 const int N=102;
  20 bool map[N][N];
  21 int n,m;
  22 int num;
  23 int step[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
  24 int ans;
  25 int Init()
  26 {
  27     scanf("%d %d",&n,&m);
  28     if(n==0&&m==0) return 0;
  29     memset(map,1,sizeof(map));
  30     for(int i=0;i<=n+1;i++)//边界设置
  31         map[i][0]=map[i][m+1]=false;
  32     for(int j=0;j<=m+1;j++)
  33         map[0][j]=map[n+1][j]=false;
  34     int x,y;
  35     scanf("%d",&num);
  36     for(int i=0;i<num;i++)
  37     {
  38         scanf("%d %d",&x,&y);
  39         map[x][y]=false;
  40     }
  41     bool flag;
  42     for(int i=1;i<=n;i++)//孤立白色单元格直接设置为黑色
  43         for(int j=1;j<=m;j++)
  44         {
  45             if(map[i][j]==false)
  46                 continue;
  47             flag=false;
  48             for(int k=0;k<4;k++)
  49             {
  50                 x=i+step[k][0];
  51                 y=j+step[k][1];
  52                 if(map[x][y]==true)
  53                 {
  54                     flag=true;
  55                     break;
  56                 }
  57             }
  58             if(flag==false)
  59             {
  60                 map[x][y]=false;
  61                 num++;
  62             }
  63         }
  64     num=n*m-num;//num为白色单元格个数
  65     ans=0;
  66     return 1;
  67 }
  68 void DFS(int d)//寻找第d+1个有效格子,即一级成功找到d个有效格子的情况下，寻找下一个
  69 {
  70     if(d>ans)
  71         ans=d;
  72     if(d+num/2<=ans)//剪枝
  73         return;
  74     int x=-1,y;
  75     for(int i=1;i<=n;i++)
  76         for(int j=1;j<=m;j++)
  77         {
  78             if(map[i][j]&&(map[i+1][j]||map[i][j+1]))
  79             {
  80                 x=i;
  81                 y=j;
  82                 i=n+1;
  83                 j=m+1;
  84             }
  85         }
  86         if(x==-1)//没有有效格子了
  87             return;
  88         if(map[x][y]&&map[x+1][y])//竖着放
  89         {
  90             map[x][y]=false;
  91             map[x+1][y]=false;
  92             num-=2;
  93             DFS(d+1);
  94             num+=2;
  95             map[x][y]=true;
  96             map[x+1][y]=true;;
  97         }
  98         if(map[x][y]&&map[x][y+1])//横着放
  99         {
 100             map[x][y]=false;
 101             map[x][y+1]=false;
 102             num-=2;
 103             DFS(d+1);
 104             num+=2;
 105             map[x][y]=true;
 106             map[x][y+1]=true;;
 107         }
 108         map[x][y]=false;//当前的白色单元格不属于任何有效格子
 109         num--;
 110         DFS(d);
 111         map[x][y]=true;
 112         num++;
 113 }
 114 int main()
 115 {
 116     while(Init())
 117     {
 118         DFS(0);
 119         printf("%d\n",ans);
 120     }
 121 }