首页 > ACM题库 > HDU-杭电 > HDU 4060-Chess Board[解题报告]HOJ
2015
04-16

HDU 4060-Chess Board[解题报告]HOJ

Chess Board

问题描述 :

allis Brook and Helen Heather like playing chess. Today they are not going to play chess buthave a competition on drawing a chess board. The chess board they used are a bit different from the ordinary one. The chess board consist of n rows and each row has m white square cells of the same size. Adjacent cells are seperated with a black border. There are also black borders on the edge of the chess board. Each border has the same width. The following figure shows how the chess board looks like. To make it like a chess board more, it is also constrained that the length of the cell should be no shorter than the width of the border, i.e. a ≥ b.
The Boss on Mars

Now they are given a black-and-white image. They are going to make it a chess board as mentioned above. They both want to finish it faster than the other one.

In order to win the competition, Vallis managed to know how Helen would draw the chess board. Each time, Helen can draw a rectangle with one color and all the pixels in the rectangle will be painted with that color. He needs time T to draw one rectangle. In addition, he will only paint each pixel with the target color. That is to say, there will be no pixel to be painted multiple times with different colors. Because Vallis is busy drawing the chess board pixel by pixel, he ask you to help him calculate the minimum time for Helen to finish the job.

输入:

There are multiple test cases. The first line of each test case contains five integers H, W, n, m and T (3 ≤ H, W ≤ 2000, 1 ≤ n, m ≤ 200, 0 < T ≤ 1000), indicating the height and the width of the image, the numbers of rows and columns and the time Helen needs to draw a rectangle. Then H lines follows, each of which contains W 0 or 1, indicating the image. 0 means the color of that pixel is black and 1 means white.

输出:

There are multiple test cases. The first line of each test case contains five integers H, W, n, m and T (3 ≤ H, W ≤ 2000, 1 ≤ n, m ≤ 200, 0 < T ≤ 1000), indicating the height and the width of the image, the numbers of rows and columns and the time Helen needs to draw a rectangle. Then H lines follows, each of which contains W 0 or 1, indicating the image. 0 means the color of that pixel is black and 1 means white.

样例输入:

3 5 1 2 1
00000
01110
01110
5 7 1 2 1
0000000
0000000
0000000
0000000
0000000

样例输出:

2
-1

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define N 2010

int h,w,n,m,t;
char s[N][N];
int sum[N][N];
int cntr[300],cntc[300];
bool map[300][300],vis[300];
int link[300];
vector<pair<int,int> >que;

bool dfs(int x)
{
	for (int i=0;i<=m;i++)
	if (!vis[i] && map[x][i])
	{
		vis[i]=1;
		if (link[i]==-1 || dfs(link[i]))
		{
			link[i]=x;
			return 1;
		}
	}
	return 0;
}

int main()
{
	while(scanf("%d%d%d%d%d",&h,&w,&n,&m,&t)!=EOF)
	{
		for (int i=0;i<h;i++)
			scanf("%s",s[i]);
		que.clear();
		if (n==m)
		{
			if (h==w)
			{
				for (int i=1;i*n<h;i++)
				{
					int x=i;
					int y=h-i*n;
					if (y%(n+1)!=0) continue;
					y/=n+1;
					if (y>x) continue;
					que.push_back(make_pair(x,y));
				}
			}
		}
		else
		{
			int x,y;
			bool flag=1;
			x=w*n-h*m;y=n-m;
			if (x%y==0) x/=y;
			else flag=0;

			int tx=h*(m+1)-w*(n+1);
			y=n-m;
			
			if (tx%y==0) y=tx/y;
			else flag=0;
			
			if (x<=0 || y<=0 || x<y) flag=0;
			if (flag && n*x+(n+1)*y==h && m*x+(m+1)*y==w)
			{
				que.push_back(make_pair(x,y));
			}
		}
		if (que.size()==0) 
		{
			printf("-1\n");
			continue;
		}
		memset(sum,0,sizeof(sum));
		for (int i=1;i<=h;i++)
		for (int j=1;j<=w;j++)
			sum[i][j]=sum[i][j-1]+sum[i-1][j]+(s[i-1][j-1]-'0')-sum[i-1][j-1];

		int ans=2100000000;

		for (int jj=0;jj<que.size();jj++)
		{
			int x=que[jj].first,y=que[jj].second,z=x+y;
			int ans1=0;
			memset(cntr,0,sizeof(cntr));
			memset(cntc,0,sizeof(cntc));
			memset(map,0,sizeof(map));
			memset(link,-1,sizeof(link));
			for (int i=1;i<=n;i++)
			for (int j=1;j<=m;j++)
			{
				int tt=sum[i*z][j*z]-sum[i*z-x][j*z]-sum[i*z][j*z-x]+sum[i*z-x][j*z-x];
				if (tt!=x*x) ans1++;
			}
			for (int i=0;i<=n;i++)
			for (int j=0;j<=m;j++)
			{
				int tt=sum[i*z+y][j*z+y]-sum[i*z][j*z+y]-sum[i*z+y][j*z]+sum[i*z][j*z];
				cntr[i]+=tt;
				cntc[j]+=tt;
			}

			for (int i=0;i<=n;i++)
			for (int j=0;j<=m;j++)
			{
				int tt=sum[i*z+y][j*z+y]-sum[i*z][j*z+y]-sum[i*z+y][j*z]+sum[i*z][j*z];
				if (!tt) continue;
				if (cntr[i]-sum[i*z+y][w]+sum[i*z][w]!=0 || cntc[j]-sum[h][j*z+y]+sum[h][j*z]!=0)
					continue;
				map[i][j]=1;
			}
			for (int i=0;i<=n;i++) if (cntr[i]-sum[i*z+y][w]+sum[i*z][w]!=0) ans1++;
			for (int i=0;i<=m;i++) if (cntc[i]-sum[h][i*z+y]+sum[h][i*z]!=0) ans1++;

			for (int i=0;i<=n;i++)
			{
				memset(vis,0,sizeof(vis));
				if (dfs(i)) ans1++;
			}
			ans=min(ans,ans1);
		}
		printf("%d\n",t*ans);
	}
	return 0;
}
/*
61 6 1
00000
01110
01110
01110
11111
11111
*/

  1. 某些人就是有很强的自卑心理,总有种中国人生产的就是差的心理。官方发布的就是假的,抨击不足的就是真实的,这种论调一直被推崇。可笑可笑

  2. 某些人就是有很强的自卑心理,总有种中国人生产的就是差的心理。官方发布的就是假的,抨击不足的就是真实的,这种论调一直被推崇。可笑可笑

  3. 某些人就是有很强的自卑心理,总有种中国人生产的就是差的心理。官方发布的就是假的,抨击不足的就是真实的,这种论调一直被推崇。可笑可笑

  4. 某些人就是有很强的自卑心理,总有种中国人生产的就是差的心理。官方发布的就是假的,抨击不足的就是真实的,这种论调一直被推崇。可笑可笑

  5. 某些人就是有很强的自卑心理,总有种中国人生产的就是差的心理。官方发布的就是假的,抨击不足的就是真实的,这种论调一直被推崇。可笑可笑

  6. 某些人就是有很强的自卑心理,总有种中国人生产的就是差的心理。官方发布的就是假的,抨击不足的就是真实的,这种论调一直被推崇。可笑可笑

  7. 某些人就是有很强的自卑心理,总有种中国人生产的就是差的心理。官方发布的就是假的,抨击不足的就是真实的,这种论调一直被推崇。可笑可笑

  8. 某些人就是有很强的自卑心理,总有种中国人生产的就是差的心理。官方发布的就是假的,抨击不足的就是真实的,这种论调一直被推崇。可笑可笑

  9. 停更了,停更了。停更了?停更了!停更了……停更了@_@停更了(>﹏<)停更了(⊙_⊙)?停更了(╯3╰)停更了╮(╯﹏╰)╭停更了╮(╯▽╰)╭停更了╭∩╮(︶︿︶)╭∩╮鄙视�停更了╭(′▽`)╯停更了╰( ̄▽ ̄)╮停更了~(≧▽≦)/~啦啦啦

  10. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  11. 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.