算法

POJ1231总结

The Alphabet Game

Description

Little Dara has recently learned how to write a few letters of the English alphabet (say k letters). He plays a game with his little sister Sara. He draws a grid on a piece of paper and writes p instances of each of the k letters in the grid cells. He then asks Sara to draw as many side-to-side horizontal and/or vertical bold lines over the grid lines as she wishes, such that in each rectangle containing no bold line, there would be p instances of one letter or nothing. For example, consider the sheet given in Figure 1, where Sara has drawn two bold lines creating four rectangles meeting the condition above. Sara wins if she succeeds in drawing the required lines. Dara being quite fair to Sara, wants to make sure that there would be at least one solution to each case he offers Sara. You are to write a program to help Dara decide on the possibility of drawing the right lines.
1231 1

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case consists of two integers k (1 <= k <= 26), the number of different letters, and p (1 <= p <= 10), the number of instances of each letter. Followed by the first line, there are k lines, one for each letter, each containing p pairs of integers (xi, yi) for 1 <= i <= p. A pair indicates coordinates of the cell on the paper where one instance of the letter is written. The coordinates of the upper left cell of the paper is assumed to be (1,1). Coordinates are positive integers less than or equal to 1,000,000. You may assume that no cell contains more than one letter.

Output

There should be one line per test case containing a single word YES or NO depending on whether the input paper can be divided successfully according to the constraints stated in the problem.

Sample Input

2
3 2
6 4 8 4
4 2 2 1
2 3 2 4
3 3
1 1 3 1 5 1
2 1 4 1 6 1
2 2 4 2 8 1

Sample Output

YES
NO

我的代码

我的想法是将所有相同的字母所占的地盘拓展成一整块矩形,这个矩形满足是包括所有该字母的最小矩形。那么分隔不同的字母就变化成分隔每一个矩形。

wechat screenshot
字母矩形

对于任意两个矩形,如果它们在一个坐标轴上的投影不重合,就可以垂直于该坐标轴画一道分割线。xy两坐标系只要满足一个这个条件就可以将两个矩形完全分开了。

那么接下来的任务就是,判断是否能沿着某一坐标系画分割线,也就是说画了这道线会不会影响到其它方块,也就是判断这条分割线是否会经过其它的方块。只需要分别求所有方块在xy轴投影的坐标,坐标范围去头去尾之后剩下来的坐标就是不可以画分割线的坐标。

以下是代码:

#include<stdio.h>
#include<string.h>
//记录每一个字母所占据的矩形范围 
struct alphabet
{
	int top,bot,left,right;
}alph[26];
int k,p;
int forbi_x[1000001]={0};//记录哪些x轴上哪些坐标不可以被分割 
int forbi_y[1000001]={0};//记录哪些y轴上哪些坐标不可以被分割 
int judge(int t)
//判断第t号字母是否能与其它的字母分隔开来,如果可以返回1,否则返回0 
{
	for (int i=t+1;i<k;i++)
	{
		int flag=0;
		if (alph[t].top>alph[i].bot)
		{
			
			for (int j=alph[i].bot;j<alph[t].top;j++)
			{
				if (!forbi_x[j])
				{
					flag=1;
					break;
				}	
			} 
		}
		if (flag) continue;
		if (alph[t].bot<alph[i].top)
		{
			for (int j=alph[t].bot;j<alph[i].top;j++)
			{
				if (!forbi_x[j])	
				{
					flag=1;
					break;
				}
			}
		}
		if (flag) continue;
		if (alph[t].left>alph[i].right)
		{
			for (int j=alph[i].right;j<alph[t].left;j++)
			{
				if (!forbi_y[j])
				{
					flag=1;
					break;
				}
			}
		}
		if (flag) continue;
		if (alph[t].right<alph[i].left)
		{
			for (int j=alph[t].right;j<alph[i].left;j++)
			{
				if (!forbi_y[j])
				{
					flag=1;
					break;
				}
			}
		}
		if (!flag)	return 0;
	}
	return 1;
}
int main()
{
	int t,x,y;
	scanf("%d",&t);
	while (t--)
	{
		int ok=1;//ok为1时此方案可行,否则不行 
		memset(forbi_x,0,sizeof(forbi_x));
		memset(forbi_y,0,sizeof(forbi_y));
		scanf("%d%d",&k,&p);
		for (int i=0;i<k;i++)
		{
			alph[i].top=1000000;
			alph[i].bot=0;
			alph[i].left=1000000;
			alph[i].right=0;
			for (int j=0;j<p;j++)
			{
				scanf("%d%d",&x,&y);
				//更新这个字母所占据的方块的大小 
				if (x<alph[i].top)	alph[i].top=x;
				if (x>alph[i].bot)	alph[i].bot=x;
				if (y<alph[i].left)	alph[i].left=y;
				if (y>alph[i].right)	alph[i].right=y;
			}
		}
		for (int i=0;i<k;i++)
		//根据每个字母所占据的方块,确定x,y轴上不能画分割线的坐标 
		{
			for (int j=alph[i].top;j<alph[i].bot;j++)
			{
				forbi_x[j]=1;
			}
			for (int j=alph[i].left;j<alph[i].right;j++)
			{
				forbi_y[j]=1;
			}
		}
		for (int i=0;i<k;i++)
		{
			if (!judge(i))	
			//如果有任何一个字母不能与任意一个其它的字母分隔,就说明这个方案不行 
			{
				ok=0;
				break;
			}				
		}
		if (ok) printf("YES\n");
		else printf("NO\n");
	}
	return 0; 
} 

另一种思路

这种思路也是分矩形。其核心思想是如果有两个矩形在坐标轴上的投影有重合的地方,就把这两个矩形的对应的变更新为投影的长度。原因是如果两个矩形投影有重合,那么相当于投影范围内都不可以画分割线,即分割线只能画在投影范围之外。于是整个投影区域内就可以看作这个字母的占据范围。

wechat screenshot 1

对所有的区域都作如上的更新之后,如果所有的矩形都不相互重合,那么就是可行的。

贴上别人的代码。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <numeric>
 
using namespace std;
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define INF 1000000000
 
int r[27], l[27], u[27], d[27];
 
bool check(int n) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(i == j) continue;
            if(((r[j] >= r[i] && r[j] <= l[i]) || (l[j] <= l[i] && l[j] >= r[i]))
                && ((u[j] >= u[i] && u[j] <= d[i]) || (d[j] <= d[i] && d[j] >= u[i])))
                    return 0;
        }
    }
    return 1;
}
 
int main() {
    int t, k ,p;
    scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &k, &p);
        for(int i = 0; i < k; i++) {
            int rr = INF, ll = 0, uu = INF, dd = 0,tmp, tmpp;
            for(int j = 0; j < p; j++) {
                scanf("%d%d", &tmp, &tmpp);
                rr = min(rr, tmp), ll = max(ll, tmp), uu = min(uu, tmpp), dd = max(dd, tmpp);
            }
            r[i] = rr, l[i] = ll, u[i] = uu, d[i] = dd;
        }
        for(int i = 0; i < k; i++) {
            for(int j = 0; j < k; j++) {
                if(i == j) continue;
                if(r[i] > r[j] && r[i] < l[j]) r[i] = r[j];
                if(l[i] < l[j] && l[i] > r[j]) l[i] = l[j];
                if(u[i] > u[j] && u[i] < d[j]) u[i] = u[j];
                if(d[i] < d[j] && d[i] > u[j]) d[i] = d[j];
            }
        }
        if(check(k)) puts("YES");
        else puts("NO");
    }
    return 0;
}

反思

对于每组样例:别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!别忘了初始化!

发表评论