首页 > ACM题库 > HDU-杭电 > HDU 1882 Strange Billboard-枚举-[解题报告] C++
2013
12-23

HDU 1882 Strange Billboard-枚举-[解题报告] C++

Strange Billboard

问题描述 :

The marketing and public-relations department of the Czech Technical University has designed a new reconfigurable mechanical Flip-Flop Bill-Board (FFBB). The billboard is a regular two-dimensional grid of R ×C square tiles made of plastic. Each plastic tile is white on one side and black on the other. The idea of the billboard is that you can create various pictures by flipping individual tiles over. Such billboards will hang above all entrances to the university and will be used to display simple pictures and advertise upcoming academic events.

To change pictures, each billboard is equipped with a ”reconfiguration device”. The device is just an ordinary long wooden stick that is used to tap the tiles. if you tap a tile, it flips over to the other side, i.e., it changes from white to black or vice versa. Do you agree this idea is very clever?

Unfortunately, the billboard makers did not realize one thing. The tiles are very close to each other and their sides touch. Whenever a tile is tapped, it takes all neighboring tiles with it and all of them flip over together. Therefore, if you want to change the color of a tile, all neighboring tiles change their color too. Neighboring tiles are those that touch each other with the whole side. All inner tiles have 4 neighbors, which means 5 tiles are flipped over when tapped. Border tiles have less neighbors, of course.

For example, if you have the billboard configuration shown in the left picture above and tap the tile marked with the cross, you will get the picture on the right. As you can see, the billboard reconfiguration is not so easy under these conditions. Your task is to find the fastest way to ”clear” the billboard, i.e., to flip all tiles to their white side.

输入:

The input consists of several billboard descriptions. Each description begins with a line containing two integer numbers R and C (1 ≤ R, C ≤ 16) specifying the billboard size. Then there are R lines, each containing C characters. The characters can be either an uppercase letter “X” (black) or a dot “.” (white). There is one empty line after each map.
The input is terminated by two zeros in place of the board size.

输出:

For each billboard, print one line containing the sentence “You have to tap T tiles.”, where T is the minimal possible number of taps needed to make all squares white. if the situation cannot be solved, output the string “Damaged billboard.” instead.

样例输入:

5 5
XX.XX
X.X.X
.XXX.
X.X.X
XX.XX
5 5
.XX.X
.....
..XXX
..X.X
..X..

1 5
...XX

5 5
...X.
...XX
.XX..
..X..
.....

8 9
..XXXXX..
.X.....X.
X..X.X..X
X.......X
X.X...X.X
X..XXX..X
.X.....X.
..XXXXX..

0 0

样例输出:

You have to tap 5 tiles.
Damaged billboard.
You have to tap 1 tiles.
You have to tap 2 tiles.
You have to tap 25 tiles.

HDU 1882 Strange Billboard

http://acm.hdu.edu.cn/showproblem.php?pid=1882

位运算+枚举

先遍历第一行的点击可能–最多有2^16种
然后接下来的行一定要点击上一行为*的点

位运算可以实现整行处理。防超时。

 

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
int r,c; //R行C列
//思路,先遍历第一行的点击可能--最多有2^16种
//然后接下来的行一定要点击上一行为*的点
int dir[5][2] = 
{
    0,0,
    0,1,
    1,0,
    -1,0,
    0,-1
};
struct Node
{
    char g[17][17];
    int b[17];
};
Node start;
Node temp;
int counter;

bool fine(int x)
{
    int i,j,k;
    int change;
    temp = start;
    for (i=0;i<r;i++)
    {
        if(i==0)
            change = x;
        else
            change = temp.b[i-1];
        temp.b[i] ^= change; //对原始行,进行原始操作,即中心点
        temp.b[i] ^= change>>1; //右边点
        temp.b[i] ^= (change<<1)&((1<<c)-1); //左边点,要去掉第一个可能超范围的“1”
        temp.b[i+1] ^= change;
        for(j=0;j<c;j++) //计算每一个的change数
        {
            if ((change >> j)&1)
                counter++;
        }
    }
    if (temp.b[r-1])
            return 0;
    return 1;
}
int main()
{
    int i,j,k,n,m,t;        
    while (scanf("%d %d",&r,&c)!=EOF)
    {
        memset(start.b,0,sizeof(start.b));
        memset(temp.b,0,sizeof(temp.b));
        if(r == 0 && c == 0)
            break;
        for (i=0;i<r;i++)
        {
            scanf ("%s",start.g[i]);
            for (j=0;j<c;j++)
            {
                if (start.g[i][j] == 'X')
                    start.b[i] = start.b[i] | (1<<(c-1-j));
            }
        }
        //----------------------------
        //for (i=0;i<r;i++)
        //    printf("%d/n",start.b[i]);
        //先遍历第一行的点击可能--最多有2^16种
        int mincount=-1;
        for (i=0;i<pow(2,c);i++) //用二进位来确定点哪个点0~(2^c-1)
        {
            counter = 0;
            if(fine(i)) //如果可以得到结果,那记录一下
            {
                if (counter < mincount || mincount == -1) //如果步数小,或求出来一个
                    mincount = counter;
            }
        }
        if (mincount == -1)
        {
            printf("Damaged billboard./n");
        }
        else
            printf("You have to tap %d tiles./n",mincount);
        memset(start.g,NULL,sizeof(start.g));
        memset(temp.g,NULL,sizeof(temp.g));
    }
    return 0;
}

 

解题报告转自:http://blog.csdn.net/jqandjq/article/details/4065181