链接:https://leetcode-cn.com/problems/perfect-rectangle/description/
题目
我们有 N 个与坐标轴对齐的矩形, 其中 N > 0, 判断它们是否能精确地覆盖一个矩形区域。
每个矩形用左下角的点和右上角的点的坐标来表示。例如, 一个单位正方形可以表示为 [1,1,2,2]。 ( 左下角的点的坐标为 (1, 1) 以及右上角的点的坐标为 (2, 2) )。
思路
首先,rectangles[][]数组里保存的每个小矩形,都有4个角.
以示例4的rectangles[0]矩形的左下角为例:
因为rectangles[0]等于{1,1,3,3},所以左下角为(1,1),处于的位置为{0,1}
所以,下面程序便通过一个 method[4][2]数组来存储4个角度的标志位,方便调用4个角出来:
int method[4][2]={{0,1},{2,3},{0,3},{2,1}}; //左下,右上,左上,右下
由于需要多个小矩形凑成的大矩形,且不能有相交区域,所以应该共有4个独立的角
比如示例1,就有4个独立的角:
而示例4,有相交区域,所以不止超过4个独立的角:
除了计算独立的角以外,还要计算矩形是否重叠过,以及核对矩形面积.
比如下例所示,同样,也是4个独立的角,不仅有相交区域,而且还不是一个矩形区域:
rectangles = [
[1,1,3,2],
[1,1,3,2],
[1,3,3,4],
]
绘制成图后:
所以在代码里,需要定义2个数组
一个用来存储角的位置,以及左下,右上,左上,右下的标志位。
另一个用来存储矩形区域的left,low,right,top的范围,用来核对面积用。
当我们每取出来一个角,都需要去匹配是否与以前的角重叠,为了效益需要用到Hash表,C语言没有Hash表函数,所以我们还需要自己来编写Hash表函数
代码如下:
#define AREA(rectang) ((rectang[3]-rectang[1])*(rectang[2]-rectang[0]))
#define Index(x,y,Hashlen) ((x*x+y*y)%Hashlen)
void Hash_Init(int Hash[][8],int len)
{
for(int i=0;i<len;i++)
{
Hash[i][7]=0;
}
}
//首先查找表,如果存在,则检查该角度是否被重叠,如果不存在,则插入表
bool Hash_search_insert(int Hash[][8],int x,int y,int angle,int *angles,int len)
{
int addr=Index(x,y,len); //求哈希地址
int tmp =addr;
//查找
while(Hash[addr][7]==1)
{
if(Hash[addr][0]==x&&Hash[addr][1]==y) //已找到
{
if(Hash[addr][angle]==0) //未重叠
{
if(Hash[addr][6]==0) // 是否 合并 过
{
Hash[addr][6]=1;
(*angles)--;
}
Hash[addr][angle]=1; //设为占用
return true;
}
else //已重叠
return false;
}
addr = (addr+1)% len;
if(addr==tmp) //未找到
return false;
}
//Hash[addr][7]等于0,说明没找到,则插入表
Hash[addr][7]=1;
Hash[addr][0]=x;
Hash[addr][1]=y;
Hash[addr][6]=0; //未合并过
(*angles)++;
for(int i=2;i<6;i++) //左下,右上,左上,右下
if(i==angle)
Hash[addr][i]=1;
else
Hash[addr][i]=0;
return true;
}
bool isRectangleCover(int** rectangles, int rectanglesRowSize, int rectanglesColSize)
{
int i,j,k,angle=0,cnt=0;
int Hashlen=rectanglesRowSize*8;
int s[Hashlen][8]; // x y 左下,右上,左上,右下 是否被合并 是否被使用
int method[4][2]={{0,1},{2,3},{0,3},{2,1}}; //左下,右上,左上,右下
int Rectangles[4]={999999,999999,-999999,-9999999}; //大矩形 left,low,right,top
unsigned long long Area; //大矩形面积
unsigned long long Fact_Area=0; //实际面积
int tmp[2]; //用来获取角的位置
Hash_Init(s,Hashlen);
for(i=0;i<rectanglesRowSize;i++)
{
Fact_Area +=AREA(rectangles[i]);
for(j=0;j<4;j++)
{
if(j<2) //计算left,low
{
if(Rectangles[j]>rectangles[i][j])
Rectangles[j]=rectangles[i][j];
}
else if(Rectangles[j]<rectangles[i][j]) //计算 right,top
Rectangles[j]=rectangles[i][j];
tmp[0]=rectangles[i][method[j][0]];
tmp[1]=rectangles[i][method[j][1]];
if(!Hash_search_insert(s,tmp[0],tmp[1],j+2,&angle,Hashlen))
return false;
}
}
if(angle!=4)
return false;
Area =AREA(Rectangles);
//printf("angle%d,Fact_Area%ld,Area%ld\n",angle,Fact_Area,Area);
if(Fact_Area==Area) //核对面积
return true;
else
return false;
}