首页 > 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. 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

  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.