题目是对RLE压缩的图像进行边缘检测。
RLE是游程编码的意思(Run length edcoding),比如555555根据游程编码可以编码成5 6。在代码中可以用控制符来区分编码字节和重复次数。
题目大意如下:
输入一张或多张游程编码的压缩图片,输出该图片的边缘检测的图片。其中,输入时0表示没有下一张图片,0 0表示本张图片输入结束。
算法思路:
1)输入的为RLE压缩图像,需要将图像还原为bitmap的形式才能计算图像的边缘检测。
缺点:如果图像过大,比如达到了10^9个像素,那么需要创建的二位数组将会超出题目给定内存的限制
优化:建立一个view,大小为3*column,这样每次只用存3行的像素,并且对于中间的一行,上下文都是可见的,因此可以做到逐行解析,逐行处理
2)根据上面的改进方法,无论多大的图像只要时间足够,都是可以计算出边缘检测图形的,但是也有缺点
缺点:逐行处理所花的时间会随着图像的增大而变多,当图形足够大的时候,时间会增到到超出限制。如果图像中重复单元很多,存在很大的优化空间。
优化:检测输入的像素,如果输入的重复像素过多,可以计算出有多少像素的边缘检测值是一样的,那么可以省去这些像素的计算
整体代码如下:
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException, InvalidInputException {
BufferedReader stdin =
new BufferedReader(
new InputStreamReader(System.in));
String line = null;
String[] input = null;
while (true) {
line = stdin.readLine();
int width = Integer.parseInt(line);
if (width == 0) break;
int[][] matrix = new int[3][width];
RlePair pair = new RlePair(0, 0);
int value = 0;
int times = 0;
int index = 0;
int delta = 0;
int diffValue = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < width; j++) {
matrix[i][j] = -1; // -1 is null
}
}
while (true) {
line = stdin.readLine();
input = line.split("\\s");
if (input.length != 2) {
throw new InvalidInputException();
}
value = Integer.parseInt(input[0]);
times = Integer.parseInt(input[1]);
if (value == 0 && times == 0) break;
int currRow = 0;
//-----------------------------------------------------------------
// 算法主体
for (int n = 0; n < times; n++) {
currRow = (index + n) / width + 1 - delta;
if (currRow == 3) {
for (int i = 0; i < width; i++) {
if (matrix[1][i] == -1) break;
diffValue = max(width, matrix, i);
if (diffValue == pair.value) {
pair.times++;
} else {
if (pair.times != 0) System.out.println(pair.toString());
pair = new RlePair(diffValue, 1);
}
}
delta++;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < width; j++) {
matrix[i][j] = matrix[i + 1][j];
}
}
currRow = (index + n) / width + 1 - delta;
if (n / width > 2 && (times - n) / width > 1) {
int d = (times - n) / width - 1;
pair.times += d * width;
n += d * width;
delta += d;
}
}
matrix[currRow][(index + n) % width] = value;
}
index += times;
}
// 算法主体
//-----------------------------------------------------------------
// 最后几行的处理
for (int i = 0; i < width; i++) {
if (matrix[1][i] == -1) break;
diffValue = max(width, matrix, i);
if (diffValue == pair.value) {
pair.times++;
} else {
if (pair.times != 0) System.out.println(pair.toString());
pair = new RlePair(diffValue, 1);
}
}
for (int i = 0; i < 2; i++) {
for (int j = 0; j < width; j++) {
matrix[i][j] = matrix[i + 1][j];
}
}
for (int j = 0; j < width; j++) {
matrix[2][j] = -1;
}
for (int i = 0; i < width; i++) {
if (matrix[1][i] == -1) break;
diffValue = max(width, matrix, i);
if (diffValue == pair.value) {
pair.times++;
} else {
if (pair.times != 0) System.out.println(pair.toString());
pair = new RlePair(diffValue, 1);
}
}
System.out.println(pair.toString());
System.out.println("0 0");
// 最后几行的处理
//-----------------------------------------------------------------
}
if (stdin != null) {
stdin.close();
stdin = null;
}
}
private static int max(int width, int[][] matrix, int index) {
// TODO Auto-generated method stub
// 0: 0 1 2
// 1: 3 4
// 2: 5 6 7
int[] x = new int[] {-1, -1, -1, -1, -1, -1, -1, -1}; // 8
if (index - 1 >= 0) {
x[0] = matrix[0][index - 1];
x[3] = matrix[1][index - 1];
x[5] = matrix[2][index - 1];
}
x[1] = matrix[0][index];
x[6] = matrix[2][index];
if (index + 1 < width) {
x[2] = matrix[0][index + 1];
x[4] = matrix[1][index + 1];
x[7] = matrix[2][index + 1];
}
int maxDiff = 0;
for (int n : x) {
if (n != -1) {
maxDiff = maxDiff > Math.abs(matrix[1][index] - n) ? maxDiff : Math.abs(matrix[1][index] - n);
}
}
return maxDiff;
}
}
class RlePair {
int value;
int times;
public RlePair(int value, int times) {
this.value = value;
this.times = times;
}
@Override
public String toString() {
// TODO Auto-generated method stub
return this.value + " " + this.times;
}
}
@SuppressWarnings("serial")
class InvalidInputException extends Exception {
}
让我郁闷的是,代码提交poj一直是runtime error,而自己测试确没什么问题。我测试的环境是jdk7.0,不知道和jdk升级是否有关系。。。(狡辩一下:我练习的目标是训练自己思考算法的感觉的,此题的目的已经达到,如果poj能多给一点错误信息我是很乐意让这道题accept的:))
分享到:
相关推荐
北大POJ1009-Edge Detection 解题报告+AC代码
poj1009 Edge Detection 可以直接AC的
2遍dp poj_3613解题报告 poj_3613解题报告
poj典型题目解题思路详解 包含源代码和解题时应注意的问题及题目陷阱设计分析
poj题目2775文件子目录源代码,递归经典题目,
poj 1699的代码和方法说明,个人原创
C_(POJ_1854)(分治).cpp
poj上第1990题目源码,用到了2个树状数组,这题数据结构是关键,想到了题目就很简单了
D_(POJ_1723)(思维)(sort).cpp
原理为:以数链思想,移动数组中的内容 使数组在没有扩充情况下,达成移动的效果 当然,有更简单的,大牛不要笑哦
D_(POJ_1723)(思维)(第k大数).cpp
POJ 3131 双向BFS解立体八数码问题
O(nlogn)凸包问题 poj2187
poj两道题的c++实现。已经测试过可以通过oj
POJ题目及算法,包括动态规划、深搜广搜等算法。含相关注释。
这是北大在线测试的第1002题,方便记忆的电话号码的解题例程,题目中有一个列表,记录着许多方便记忆的电话号码。不同的方便记忆的电话号码可能对应相同的标准号码,这个程序的任务就是找到它们
问题:求平面上多个矩形的总面积。 算法:线段树(经典的线段树题目)
poj 3310 的代码和方法说明,个人原创
http://poj.grids.cn/problem?id=2774 POJ 2774 木棒加工 木材厂有一些原木,现在想把这些木头切割成一些长度相同的小段木头,需要得到的小段的数目是给定了。当然,我们希望得到的小段越长越好,你的任务是计算能够...
看了测试用例后,大家估计已经明白题目的意思了吧!题目很简单,但是就是很烦。 开始直接是没思路,不知道怎么模拟,但是想了带该半个小时,就搞定了。就是把每个数存到数组里面。