问题3147--3-1 坏苹果

3147: 3-1 坏苹果

时间限制: 2 Sec  内存限制: 256 MB
提交: 22  解决: 3
[状态] [讨论版] [提交] [命题人:]
题目描述

空梦闲暇时间用 Kotlin 基于 JNI 写了一个 JVM 端的操作 Windows 控制台的库,通过这个库我们便可以在 JVM 中操作控制台。

为了展示库的功能,空梦决定使用这个库编写一个应用程序——在控制台播放“Bad Apple”。


空梦很快就写好了最基本的代码,但是非常遗憾的是,由于 JNI 存在一些性能损失,空梦逐帧绘制时出现了明显的卡顿,这段程序很显然是需要进行优化的。

空梦想出了两种优化方式:

  1. 多线程优化

  2. 画布重用

多线程优化顾名思义就是多个线程同时绘制一帧或多帧,以此更加充分的利用 CPU 的各个核心的性能;画布重用就是绘制当前帧时不重置画布,而是在上一帧(如果使用了多级缓存则需要在前 N - 1 帧)的基础上进行绘制,仅重绘两帧之间不同的像素。

这两种优化方法的思路都是可行的,前者尝试通过多线程技术优化程序性能,后者则尝试通过改变程序逻辑来优化性能。

经过一番抉择,空梦决定使用“画布重用”来进行优化,但是由于空梦太笨,没有搞定如何计算两帧之间的不同的区域,并推导出一个最优的重绘方案,现在他来寻求参加天梯赛的各位佬的帮助,希望佬们能够帮助他解决这个问题。

空梦已经为控制台建好了坐标系,坐标系原点位于控制台的左上角,X 轴向右为正,Y 轴向下为正,原点的坐标为 (0, 0);同时他也已经对图像进行了预处理,将“Bad Apple”的每一帧都转换为了灰度图像(RGB 图像具有三个通道,灰度图像仅有一个通道),并规定了区分亮色与暗色像素的分界线,大于等于 128 的像素认为是亮色,小于 128 的像素认为是暗色。

需要注意的是,控制台在绘制颜色时只能横向绘制,不能纵向绘制(即每次填充的矩形的高度只能为 1),绘制区域超过当前行的范围时会自动换行

假设我们现在有一个背景为亮色、长宽为 3 × 3 的画布:

222, 255, 160
128, 200, 255
233, 255, 151

现在我们要在 (0, 1) 的位置填充一个宽 4 的暗色矩形,填充后的结果为:

222, 255, 160
000, 000, 000
000, 255, 151

现在请你写一个程序,比较两帧的画面的差异,在保证填充区域最小的情况下,计算出绘制操作数量最少的方案。

输入

第一行输入两个正整数 n, m (1 ≤ n, m ≤ 500),其中 n 表示画布的宽,m 表示画布的高。

接下来 m 行每行 n 个非负整数,表示上一帧当前行的各个像素的灰度值 Ai,j,两两之间使用逗号间隔(行末没有逗号)。

接下来 m 行每行 n 个非负整数,表示要绘制的这一帧的当前行的各个像素的灰度值 Bi,j,两两之间使用逗号间隔(行末没有逗号)。

注:输入的每个灰度值 Ai,j, Bi,j 均为三位整数,有前缀 0,∀Ai,j, Bi,j ∈ {000, 001, 002, ... , 255}。保证最后一行数据行末包含换行符。

输出

先输出一行一个正整数 k,表示最少的操作数。

然后输出 k 行,每行表示一个绘制操作,一个绘制操作的格式如下:

x, y, color, width

其中 "x, y" 表示这个绘制操作起始的坐标点,"color" 表示要绘制的颜色("BLACK" 或 "WHITE",其中 "BLACK" 代表暗色,"WHITE" 代表亮色),"width" 表示绘制的宽度。

注意:逗号后包含一个空格,行末没有逗号。

输出时按绘制操作的起始坐标进行排序,逐行扫描(从左到右,从上到下)先扫描到的点先输出。

样例输入 Copy
3 3
222,255,160
128,200,255
233,255,151
222,255,160
000,000,000
000,255,151
样例输出 Copy
1
0, 1, BLACK, 4
提示

样例输入 2:

5 5
001,002,003,004,005
201,202,203,204,205
125,126,127,128,129
128,127,126,125,124
000,111,222,233,255
255,233,222,111,000
128,127,126,125,124
129,128,127,126,125
201,202,203,204,205
005,004,003,002,001

样例输出 2:

6
0, 0, WHITE, 3
1, 1, BLACK, 4
0, 2, WHITE, 2
3, 2, BLACK, 2
1, 3, WHITE, 4
2, 4, BLACK, 3

样例解释:

在样例输入 1 中,需要修改的坐标是 (0, 1), (1, 1), (2, 1), (0, 2),均为亮色改为暗色,所以我们在 (0, 1) 填充一个宽度为 4 的暗色矩形即可