首页 > 代码库 > SJTU 1319. countColors

SJTU 1319. countColors

题目描述

知道 psypaint 怎么用吗?在巫女系统全面普及的未来世界,很少人会知道 psypaint 的用法。而身处在公安局作为监视官的朱同学,为了办案需要研究起了 psypaint 的用法。

现在朱面前的显示屏上是 psypaint 的操作画面。画面上有一张纯白色画布,画布可以根据需要无限延伸。

现在剪贴板里有一张 n*m 像素的图片,图片上有些像素有颜色,没颜色的地方则是透明的。颜色有 3 种,分别用 R,G,B 表示,而透明则用’ . ’表示。第一次粘贴操作,剪贴板会以画布(1,1)位置为图片的左上角把图片粘贴上去,第二次粘贴操作则以(2,2)为左上角,以此类推。注意到图片有颜色的地方会覆盖掉画布原有位置的颜色,而透明则显示的还是原来画布的颜色。现在朱同学不小心按了 T 次粘贴操作,请问 T 次操作之后颜色为 R,G,B 的像素各有多少个。

输入格式

第一行 n,m

接下来是一个 n*m 的字符矩阵,描述了剪贴板里的图片

最后一行是 T

输出格式

一行输出 3 个数,用空格隔开为 R,G,B 颜色像素的数量。

输入样例

3 3
..G
R..
BG.
3

输出样例

3 4 3

数据约定

对于 30%数据 T<=50

对于所有数据保证 1<=n,m<=50,1<=T<=10^9

思路:先动手写几个,发现规律,我们从斜线考虑,如果在出现R,G,B之前还没有出现‘.’的话,那么由于覆盖的话,那么这些将出现t次,然后就是先出现过像素的话,那么接下出现的像素不会被覆盖掉,所以也要考虑。至于都是空白的话,就是不考虑了

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
typedef long long ll;
using namespace std;
const int maxn = 60;

int n, m, t;
char g[55][55];
ll ans[3];

void deal(int x, int y) {
	int flag = 0;
	int tmp = 1;
	while (g[x][y] != 0) {
		if (flag) {
			if (g[x][y] == '.') tmp++;
			else {
				if (g[x][y] == 'R') ans[0] += min(t, tmp);
				else if (g[x][y] == 'G') ans[1] += min(t, tmp);
				else if (g[x][y == 'B']) ans[2] += min(t, tmp);
				tmp = 1;
			}
		} else if (g[x][y] != '.') {
			if (g[x][y] == 'R') ans[0] += t;
			else if (g[x][y] == 'G') ans[1] += t;
			else if (g[x][y] == 'B') ans[2] += t;
			flag = 1;
		}
		x++;
		y++;
	}
}

int main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		memset(g, 0, sizeof(g));
		memset(ans, 0, sizeof(ans));
		for (int i = 0; i < n; i++)
			scanf("%s", g[i]);
		scanf("%d", &t);

		for (int i = 0; i < n; i++) 
			deal(i, 0);
		for (int i = 1; i < m; i++)
			deal(0, i);
		printf("%lld %lld %lld\n", ans[0], ans[1], ans[2]);
	}
	return 0;
}


SJTU 1319. countColors