铺地毯题解

这里附上题目链接：铺地毯。

							~~手动分割~~

题目

							~~手动分割~~

思路解析

1.倒搜

越在后面放入的地毯就越有可能覆盖在所求格子的最上面，所以直接倒搜：

1. 若发现所求点在当前地毯的覆盖范围内，则说明当前地毯一定是覆盖在所求点的最上面，输出编号，结束程序；
2. 若发现所求点没有被地毯覆盖，输出-1.

AC代码：

#include <stdio.h>
#include <stdlib.h>int map[10000][4];int main()
{int n,a,b,g,k,i,x,y;//输入数据scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d%d%d",&a,&b,&g,&k);map[i][0]=a;//地毯左上角行坐标map[i][1]=b;//地毯左上角列坐标map[i][2]=a+g;//地毯右下角行坐标map[i][3]=b+k;//地毯右下角列坐标}scanf("%d%d",&x,&y);//输入所求点坐标for(i=n;i>=1;i--)//倒搜{if(x>=map[i][0]&&x<=map[i][2]&&y>=map[i][1]&&y<=map[i][3])//若所求点在当前地毯的覆盖范围内{printf("%d",i);return 0;}}printf("-1");return 0;
}

2.暴力标记法

1. 建立一个二维数组map[ ] [ ]来记录覆盖在每一格最上面的地毯的编号；
2. （一共有n条地毯）每输入一条地毯的覆盖范围，便将覆盖范围内的格子最上面的地毯更新；
3. 若没有地毯覆盖在所求地面的点上面，输出 -1；
   否则输出覆盖在最上面的地毯的编号。

缺点：时间复杂度过高，不能AC！

代码：

#include <stdio.h>
#include <stdlib.h>int map[10000][10000];int main()
{int n,m,a,b,g,k,i,j,x,y;//输入数据scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d%d%d%d",&a,&b,&g,&k);for(j=a;j<=a+g;j++){for(m=b;m<=b+k;m++){map[j][m]=i;}}}scanf("%d%d",&x,&y);if(!map[x][y]){printf("-1");}else{printf("%d",map[x][y]);}return 0;
}

						~~手动分割~~