首页 > ACM题库 > HDU-杭电 > HDU 3935-Dark Room[解题报告]HOJ
2015
04-14

HDU 3935-Dark Room[解题报告]HOJ

Dark Room

问题描述 :

One day Harry Potter came to a magic room, in which there are some shadow monsters sent by the black wizard waiting for him. Fortunately, shadow monsters can only live in areas where there are no lights shining, there are n*m lamps on the roof of the room, every little lamp can only illuminate the scope of the fixed area, and all the area of lights shining don’t overlap, some lamps on, some lamps off, the areas below the closed lamps will appear the shadow, and in these areas shadow monsters will attack Harry Potter. Now Harry Potter comes to you and gives you the previous state of the room lights, Harry Potter can control the light switch in a remote place .The state of a light will change as follows: if a lamp state changed, the state of the lights which before it, after it, left to it or right to it will all change. Your task is to calculate how many times we need at least to turn on all the lights by changing the state of the lamps.

输入:

in the first line there are two integers, n (1 < = n < = 100) and m (1 < = m < = 15), stands for there are n lines, each line have m data, 0 stands for the lights off, 1 stands for the lights on.

输出:

in the first line there are two integers, n (1 < = n < = 100) and m (1 < = m < = 15), stands for there are n lines, each line have m data, 0 stands for the lights off, 1 stands for the lights on.

样例输入:

3 3
1 0 1
0 0 0
1 0 1

样例输出:

1

#include<cstdio>
#include<cstring>

int row[101],ans;
int m,n;

int cnt(int v)
{
	int sum=0;

	for(int i=0;i<m;i++)
	{
		sum+=v&1;
		v>>=1;
	}
	return sum;
}

void check(int v)
{
	int sum=cnt(v);
	int tmp,last=0,tool=0;

	for(int i=0;i<m;i++)
	{
		tool<<=1;
		tool|=1;
	}
	for(int i=2;i<=n;i++)
	{
		tmp=last^v^v<<1^v>>1^row[i-1];
		last=v;
		v=tmp;
		v&=tool;
		sum+=cnt(v);
	}
	if(cnt(v>>1^v^v<<1^last^row[n])==0)
	{
		if(ans>sum)
		{
			ans=sum;
		}
	}
}
void solve(int c,int v)
{
	if(c<m)
	{
		solve(c+1,v<<1|1);
		solve(c+1,v<<1);
	}
	else
	{
		check(v);
	}
}
void read(int i)
{
	int tmp;
	for(int j=1;j<=m;j++)
	{
		row[i]<<=1;
		scanf("%d",&tmp);
		row[i]^=tmp^1;
	}
}

int main()
{
	while(~scanf("%d %d",&n,&m))
	{	
		memset(row,0,sizeof(row));
		ans=0x7fffffff;

		for(int i=1;i<=n;i++)
		{
			read(i);
		}

		solve(1,0);
		solve(1,1);

		if(ans^0x7fffffff)
		{
			printf("%d\n",ans);
		}
		else
		{
			puts("no solution");
		}
	}
	return 0;
}

  1. 我没看懂题目
    2
    5 6 -1 5 4 -7
    7 0 6 -1 1 -6 7 -5
    我觉得第一个应该是5 6 -1 5 4 输出是19 5 4
    第二个是7 0 6 -1 1 -6 7输出是14 7 7
    不知道题目例子是怎么得出来的

  2. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.