文章目录
- CSDN竞赛62期分析
- 1.给定两个矩形的坐标求两个矩形的覆盖面积
- 题目说明
- 题目分析
- 代码
- 2.坐标轴移动是否能达到终点的问题
- 题目说明
- 输入格式
- 题目分析
- 代码
CSDN竞赛62期分析
第一次参加CSDN周赛，表现真的是一塌糊涂，所以把题目记下来，有空慢慢做。
打算以后把每一期的题目都做一遍
1.给定两个矩形的坐标求两个矩形的覆盖面积
题目说明
给你二维平面上两个由直线构成目边与坐标轴平行/垂直的矩形，请你计算并返回两个矩形覆盖的总面积。每个矩形由其左下顶点和右上顶点坐标表示:
第一个矩形由其左下顶点(ax1,ay1)和右上顶点(ax2,ay2)定义。第二个矩形由其左下顶点(bx1,by1)和右上顶点(bx2，by2)定义
参数限制：-10e4 <= ax1,ay1,ax2,ay2,bx1,by1,bx2,by2 <= 10e4
题目分析
覆盖面积=两个矩形的面积相加然后减去重叠面积
本质上是求两个矩形的重叠面积
这个需要自己画个图，慢慢体会一下，重叠矩形的宽是bx2和ax2的最小值减去bx1和ax1的最大值，同理，矩形的高是by2和ay2的最小值减去by1和ay1的最大值
代码
#include <stdio.h>#define min(x,y) ((x) < (y)? (x) : (y))
#define max(x,y) ((x) > (y)? (x) : (y))// 求重合的面积
int get_coverage_area(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2, int by2)
{int width = max(0, min(bx2, ax2) - max(bx1, ax1)); // 重叠矩形的宽int height = max(0, min(by2, ay2) - max(by1, ay1));return width * height;
}
2.坐标轴移动是否能达到终点的问题
题目说明
小光买了一个可编程机器猫，机器猫初始位置在原点(0,0)。小伙伴事先给机器猫输入一串指令command，机器猫就会无限循环这条指今的步强进行移动。
指今有四种：U:向y轴正方向移动一格，R:向x轴正方向移动一格，D:向y轴负方向移动一格，L:向x轴负方向移动一格
不幸的是，在平面上还有一些遮挡物，他们的坐标用 barriers 表示。机器猫一旦碰到遮挡物就会被损毁。
给出command、barriers数组以及终点坐标，问：机器猫是否能安全到达终点
输入格式
这个CSDN周赛题的输入方式对使用C语言太不友好了，从输入字符串中解析出每个参数都要费很大的功夫，这里就不写了
题目分析
首先命令是循环的，每次循环都会到达一个点，这些点分别为A1,A2…An. 因为是命令是循环的，这些点一定是在一条直线上的断续的点。
在第一个命令循环中，我们可以得到两个信息
1.能够得到一个终点坐标a1,a1和原点确定一条直线，每一次循环的终点坐标就确定了，循环终点坐标确定，相当于起点坐标也确定了，因为起点坐标是前一次循环的终点坐标
2.在第一个命令循环中，也可以得到一次循环中，走过的路径中，相对于起点坐标在x轴和y轴4个方向的最大偏移量为u,d,l,r。
有了这两个信息，我们不用穷举每一次机器猫走过的路径，只要遍历可能经过障碍点和终点的某次循环就行了。
比如：每一次循环后的终点坐标是(2,3) f(n)=(2n,3n) ，最大偏移量：u=3，d=2,l=1,5，那么，每次循环可能经过的路径就在一个矩形之中，这个矩形的左下角坐标为(2n-l,3n-d),矩形的右上角坐标是(2n+r,3n+u)，终点坐标是(x,y)，只要在 2n-l <= x <= 3n+r and 2n-d <= y <= 3n+u的那次循环中，才有可能到终点。同理，障碍物坐标也是这样。
代码
#include <stdio.h>
#include <stdbool.h>
#include <math.h>#define min(x,y) ((x)<(y)? (x) : (y))
#define max(x,y) ((x)>(y)? (x) : (y))
#define coordinate_same(x1,y1,x2,y2) ((x1) == (x2) && (y1) == (y2))// 移动后的坐标
#define MOVE(cmd,x,y) \
{\switch(cmd)\{\case 'U':\y += 1;\break;\case 'D':\y -= 1;\break;\case 'L':\x -= 1;\break;\case 'R':\x += 1;\break;\} \
}// 计算第几个循环可能经过某个坐标，n是一个范围
void get_cycle_num(int dest_x, int dest_y, int x1, int y1, int l, int r, int d,int u, int *n_min, int * n_max)
{// (x1*n-l <= x <= x1*n+r) and (y1*n-d <= y <= y1*n + u)int xn_max = (dest_x+l)/x1; // x轴的n的最大值int xn_min = (dest_x-r)/x1; int yn_max = (dest_y+d)/y1; // y轴的n的最大值int yn_min = (dest_y-u)/y1;*n_max = min(xn_max, yn_max); // 综合x轴和y轴，n可以取的最大值*n_min = max(xn_min, yn_min);printf("xn_min=%d,xn_max=%d,yn_min=%d,yn_max=%d,n_min=%d,n_max=%d\n",xn_min,xn_max,yn_min,yn_max,*n_min,*n_max);
}// 检查当前坐标是否是终点或者是障碍物坐标
// return: 0:都不是 1：是终点 2：是障碍物
int check_dest_and_obstacle(int x, int y, int dest_x, int dest_y, int barriers_x[],int barriers_y[], int barrier_num)
{if (coordinate_same(x,y,dest_x,dest_y))return 1;for (int i = 0; i < barrier_num; i++){if (coordinate_same(x,y,barriers_x[i],barriers_y[i]))return 2;}return 0;
}/*** @函数名称: can_arrive_destination* @功能描述: 判断是否能到达终点* @输入参数: * command: 指令集，U:向y轴正方向移动一格，R:向x轴正方向移动一格，D:向y轴负方向移动一格，L:向x轴负方向移动一格* dest_x,dest_y： 终点坐标* barriers_x,barriers_y： 障碍物的x坐标和y坐标* barrier_num： 障碍物的个数*/
bool can_arrive_destination(char *command, int dest_x, int dest_y, int barriers_x[],int barriers_y[], int barrier_num)
{int x, y; // 当前坐标int x1, y1; // 第一次命令执行后的位置int start_x = 0, start_y = 0; // 初始点坐标int d = 0, u = 0, l = 0, r = 0;char *p;int x_shift, y_shift;// 1.计算第一次执行完整命令后移动的终点和各个方向的偏移量p = command;x = start_x;y = start_y;int count = 0;while(*p){MOVE(*p,x,y);x_shift = x - start_x;y_shift = y - start_y;if (x_shift > 0 && x_shift > r)r = x_shift;else if (x_shift < 0 && -x_shift > l)l = -x_shift;if (y_shift > 0 && y_shift > u)u = y_shift;else if (y_shift < 0 && -y_shift > d)d = -y_shift;// printf("%c,x=%d,y=%d\n",*p,x,y);p++;count++;}x1 = x;y1 = y;printf("first move:(%d,%d),u=%d,d=%d,l=%d,r=%d\n",x,y,u,d,l,r);// 2.计算终点是在第几次命令循环int n_min, n_max;get_cycle_num(dest_x,dest_y,x1,y1,l,r,d,u,&n_min,&n_max);// 如果没有满足的n，则说明一定走不到终点if (n_max < n_min)return false;// 3.在可能经过终点的循环中遍历是否能到达终点bool succ = false;for (int n = n_min; n <= n_max; n++){x = x1 * n;y = y1 * n;p = command;// 使用do while是因为需要检查起点坐标do{int res = check_dest_and_obstacle(x,y,dest_x,dest_y,barriers_x,barriers_y,barrier_num);if (1 == res){succ = true;break;}else if (2 == res) // 会经过障碍物，直接失败{return false;}MOVE(*p,x,y);p++;}while(*p);if (true == succ)break;}// printf("000000000\n");if (!succ)return false;// 4.即使第n次循环能到达终点，但是如果第1-(n-1)次循环经过了障碍物也不能到达终点int barrier_min_n[200]; // 这里可以申请动态内存来节省空间和避免越界，200已经满足题目的要求了int barrier_max_n[200];int barrier_n_upper = n_min - 1; // 循环上限// 计算可能经过障碍物是第几次循环for (int i = 0; i < barrier_num; i++){// 4.1计算每个障碍物是在第几次命令循环中可能到达的int n_min, n_max;get_cycle_num(barriers_x[i],barriers_y[i],x1,y1,l,r,d,u,&n_min,&n_max);// n的范围必须小于 barrier_n_upperif (n_max < n_min || n_min > barrier_n_upper){barrier_min_n[i] = -1; // 用-1表示不能能经过障碍物 barrier_max_n[i] = -1;}else{barrier_min_n[i] = n_min;barrier_max_n[i] = min(n_max, barrier_n_upper);}}for (int i = 0; i < barrier_num; i++){if (-1 == barrier_min_n[i])continue;// 检查是否经过障碍物for (int n = barrier_min_n[i]; n <= barrier_max_n[i]; n++){x = x1 * n;y = y1 * n;p = command;do{if (coordinate_same(x,y,barriers_x[i],barriers_y[i]))return false;MOVE(*p,x,y);p++;}while(*p);}}return true;
}int main()
{char command[] = "URR"; // 命令int x = 3, y = 2; // 终点坐标int barriers_x[200] = {2}; // 障碍物x轴坐标int barriers_y[200] = {2}; // 障碍物y轴坐标int barrier_num = 1; // 障碍物坐标的个数if (can_arrive_destination(command,x,y,barriers_x,barriers_y,barrier_num))printf("true");elseprintf("false");return 0;
}
