题目链接:uva 1493 - Draw a Mess
题目大意:给定一个矩形范围,有四种上色方式,后面上色回将前面的颜色覆盖,最后问9种颜色各占多少的区域。
解题思路:用并查集维护每个位置对应下一个可以上色的位置。然后将上色倒转过来处理,就解决了颜色覆盖的问题。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxr = 205;
const int maxc = 50005;
int N, M, Q, cnt[15];
int f[maxr][maxc];
struct Order {
int sign, star, end;
int x, y, r, w, c;
void set (int sign, int x, int y, int c, int r, int w = 0) {
this->sign = sign;
this->x = x;
this->y = y;
this->c = c;
this->r = r;
this->w = w;
del_star();
}
void del_star () {
if (sign < 2) {
star = max(x - r, 0);
end = min(x + r, N - 1);
} else if (sign == 2) {
r = (r + 1) / 2 - 1;
star = x;
end = min(x + r, N-1);
}
}
}op[maxc];
int getfar (int* far, int x) {
return x == far[x] ? x : far[x] = getfar(far, far[x]);
}
int style (char ch) {
if (ch == 'C')
return 0;
else if (ch == 'D')
return 1;
else if (ch == 'T')
return 2;
else
return 3;
}
void init () {
memset(cnt, 0, sizeof(cnt));
for (int i = 0; i <= M; i++) {
for (int j = 0; j < N; j++)
f[j][i] = i;
}
char s[20];
int x, y, r, c, w;
for (int i = 1; i <= Q; i++) {
scanf("%s", s);
if (s[0] != 'R') {
scanf("%d%d%d%d", &x, &y, &r, &c);
op[i].set(style(s[0]), x, y, c, r);
} else {
scanf("%d%d%d%d%d", &x, &y, &r, &w, &c);
op[i].set(style(s[0]), x, y, c, r, w);
}
}
}
inline int get_R (int r, int x, int i, int sign) {
if (sign == 0)
return (int)sqrt(1.0 * r * r - 1.0 * (x - i) * (x - i));
else if (sign == 1)
return r - abs(x - i);
else if (sign == 2)
return r - (i - x);
return 0;
}
int count (int x, int y, int r, int star, int end, int sign) {
int ret = 0;
for (int i = star; i <= end; i++) {
int R = get_R(r, x, i, sign);
int mv = max(y - R, 0);
while (mv = getfar(f[i], mv), abs(mv - y) <= R && mv < M) {
ret++;
f[i][mv] = mv+1;
}
}
return ret;
}
int count_rec (int x, int y, int r, int l) {
int ret = 0;
for (int i = x; i <= x + r - 1 && i < N; i++) {
int mv = y;
while (mv = getfar(f[i], mv), abs(mv - y) < l && mv < M) {
ret++;
f[i][mv] = mv+1;
}
}
return ret;
}
void solve () {
for (int i = Q; i; i--) {
int& col = cnt[op[i].c];
if (op[i].sign == 3)
col += count_rec(op[i].x, op[i].y, op[i].r, op[i].w);
else
col += count(op[i].x, op[i].y, op[i].r, op[i].star, op[i].end, op[i].sign);
}
for (int i = 1; i <= 9; i++)
printf("%d%c", cnt[i], i == 9 ? '\n' : ' ');
}
int main () {
while (scanf("%d%d%d", &N, &M, &Q) == 3) {
init();
solve();
}
return 0;
}
分享到:
相关推荐
查看电脑信息
利用proteus进行仿真,内含有代码和项目文件,导入即可,还有keil编程,可以实现实体硬件的烧录
欢迎来到混乱管理系统 :waving_hand: 基于Python Flask后端的混乱管理系统 :sparkles: 安装 docker-compose up 用法 docker-compose build 运行测试 docker-compose run web pytest 作者 :bust_in_silhouette: ...
流星模板与数据的动态混乱 流星模板与数据的动态混乱
资源分类:Python库 所属语言:Python 使用前提:需要解压 资源全名:py_mess_server_kuznetsov-3.3.5-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
This book provides a seven step process for making sense of any mess. Each chapter contains a set of lessons as well as workbook exercises architected to help you to work through your own mess.
C# 与 三菱PLC 通讯源代码,欢迎下载
五年级下册What a mess BMU时上海牛津PPT课件.pptx
wap标准协议中push message 的介绍,详细介绍push message的原理
jason-mess-around
redis学习——(发布订阅)简单易懂demo
资源分类:Python库 所属语言:Python 资源全名:mess_client_makeev-0.0.1.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
python库。 资源全名:client_mess_proj-0.0.2-py3-none-any.whl
another junk to mess with :)
食堂模拟程序,用到了类的继承和派生,方便同学学习和使用
语言:English (United States) ... 新妈妈和旅行者必须处理两个主要问题:混乱,并清理自己的便盆嘴。 为什么不使用两者湿润的优势? 湿润的是创造了这一点,以帮助你清理你的****。 再也不会看到“M”字。
4号旅馆-混乱扩展 这是4号旅馆-IIT孟买4号旅馆的囚犯的杂乱菜单扩展。 特点:-随时查看“混乱”菜单。 -菜单将自动在线同步。 因此,无需重新安装扩展程序。 -收藏您最喜欢的一餐。...-您会收到有关您加餐的通知。...
upload2 pdf mess