|
|
Posted on 2008-03-28 10:23 王大头 阅读(771) 评论(1) 编辑 收藏 引用
Edge Detection(ACM 1009)
Time Limit:1000MS Memory Limit:10000K
Total Submit:3035 Accepted:595
Description
IONU Satellite Imaging, Inc. records and stores very large images using run length encoding. You are to write a program that reads a compressed image, finds the edges in the image, as described below, and outputs another compressed image of the detected edges.
A simple edge detection algorithm sets an output pixel's value to be the maximum absolute value of the differences between it and all its surrounding pixels in the input image. Consider the input image below:
The upper left pixel in the output image is the maximum of the values |15-15|,|15-100|, and |15-100|, which is 85. The pixel in the 4th row, 2nd column is computed as the maximum of |175-100|, |175-100|, |175-100|, |175-175|, |175-25|, |175-175|,|175-175|, and |175-25|, which is 150.
Images contain 2 to 1,000,000,000 (109) pixels. All images are encoded using run length encoding (RLE). This is a sequence of pairs, containing pixel value (0-255) and run length (1-109). Input images have at most 1,000 of these pairs. Successive pairs have different pixel values. All lines in an image contain the same number of pixels.
Input
Input consists of information for one or more images. Each image starts with the width, in pixels, of each image line. This is followed by the RLE pairs, one pair per line. A line with 0 0 indicates the end of the data for that image. An image width of 0 indicates there are no more images to process. The first image in the example input encodes the 5x7 input image above.
Output
Output is a series of edge-detected images, in the same format as the input images, except that there may be more than 1,000 RLE pairs.
 #include <stdio.h>
#define ABS(x) (x < 0) ? (-1 * x) : (x)
#define MAX(x, y) (x > y) ? (x) : (y)
#define MIN(x, y) (x < y) ? (x) : (y)
int L, C, P, IMG[1024][3], OIMG[2048][3];
int get_value(int p ,int a) {
int h = C, l = 0, m;
if(p < 1 || p >= P)
return(-1);
do {
m = (h + l) / 2;
if(IMG[m][0] <= p && IMG[m][1] >= p) {
if(a <= 2 && a >= 0)
return(IMG[m][a]);
else
return(m);
}
else if(IMG[m][0] > p)
h = m;
else
l = m;
} while(h > l);
}
int same_value(int s, int e) {
int h = C, l = 0, m;
if(e < 1)
return(0);
if(s >= P)
return(0);
for(m = 0; m < C; m++) {
if(IMG[m][0] <= s) {
if(IMG[m][1] >= e)
return(0);
else
return(-1);
}
}
return(-1);
}
int get_step(int j) {
int a, b, c, d, e, f, g, ret;
e = (j - 1) / L;
a = (e - 1) * L + 1;
b = (e - 1) * L + L;
c = (e + 1) * L + 1;
d = (e + 1) * L + L;
e = e * L + L - 1;
f = get_value(j, 1) - 1;
g = get_value(j, 0);
if(g == j)
ret = j;
else if((same_value(a, b) == 0)
&& (same_value(c, d) == 0)
&& (MIN(e, f) > j))
ret = MIN(e, f);
else
ret = j + 1;
return(ret);
}
int max_value(int p) {
int v, t, m = -1;
v = get_value(p, 2);
if(p > L && p % L != 1 && -1 != (t = get_value(p - L - 1, 2))) {
t = ABS((v - t));
m = MAX(m, t);
}
if(p > L && -1 != (t = get_value(p - L, 2))) {
t = ABS((v - t));
m = MAX(m, t);
}
if(p > L && p % L != 0&& -1 != (t = get_value(p - L + 1, 2))) {
t = ABS((v - t));
m = MAX(m, t);
}
if(p % L != 1 && -1 != (t = get_value(p - 1, 2))) {
t = ABS((v - t));
m = MAX(m, t);
}
if(p % L != 0 && -1 != (t = get_value(p + 1, 2))) {
t = ABS((v - t));
m = MAX(m, t);
}
if(p < P && p % L != 1 && -1 != (t = get_value(p + L - 1, 2))) {
t = ABS((v - t));
m = MAX(m, t);
}
if(p < P && -1 != (t = get_value(p + L, 2))) {
t = ABS((v - t));
m = MAX(m, t);
}
if(p < P && p % L != 0 && -1 != (t = get_value(p + L + 1, 2))) {
t = ABS((v - t));
m = MAX(m, t);
}
return(m);
}
int main() {
int v, l, p, i, j, c, t, begin, end;
while(fscanf(stdin, "%d", &L) != EOF) {
if(L == 0) {
printf("0\n");
break;
}
C = 0;
P = 1;
while(fscanf(stdin, "%d %d", &v, &l) != EOF) {
IMG[C][0] = P;
IMG[C][1] = P + l - 1;
IMG[C][2] = v;
P = P + l;
if(l == 0)
break;
C++;
}
for(i = 0; i < C * 2; OIMG[i][0] = OIMG[i][1] = OIMG[i][2] = -1, i++);
for(i = 0, c = 0, p = 1; i < C;) {
begin = IMG[i][0] - L - 1;
begin = MAX(begin, 1);
end = IMG[i][0] + L + 1;
end = MIN(end, P);
for(j = begin; j < end;) {
if(j < 1 || j >= P || j < p) {
j++;
continue;
}
v = max_value(j);
if(OIMG[c][2] == v)
OIMG[c][1] = j;
else {
if(OIMG[c][2] != -1)
c++;
OIMG[c][0] = j;
OIMG[c][1] = j;
OIMG[c][2] = v;
}
p = j + 1;
t = get_step(j);
j = (t < p) ? (j + 1) : t;
i = get_value(j, 3);
}
begin = IMG[i][1] - L - 1;
begin = MAX(begin, p);
end = IMG[i][1] + L + 1;
end = MIN(end, P);
for(j = begin; j < end;) {
if(j < 1 || j >= P || j < p) {
j++;
continue;
}
v = max_value(j);
if(OIMG[c][2] == v)
OIMG[c][1] = j;
else {
if(OIMG[c][2] != -1)
c++;
OIMG[c][0] = j;
OIMG[c][1] = j;
OIMG[c][2] = v;
}
p = j + 1;
t = get_step(j);
j = (t < p) ? (j + 1) : t;
i = get_value(j, 3);
}
if(j > P - 1)
break;
}
printf("%d\n", L);
for(i = 0; i <= c; i++) {
printf("%d %d\n", OIMG[i][2], (OIMG[i][1] - OIMG[i][0] + 1));
}
printf("0 0\n");
}
}
这道题变态之处在于步长很难控制，还有就是结束的时候需要打印一个"0"再退出。是在是bt至极。 乱七八糟写了这么多，执行速度在C里面还是倒数第三…… -_-!!!
Feedback
# re: 1009@poj 回复 更多评论
2011-06-24 18:02 by
你的几个宏都应加上括号吧
#define MIN(x, y) (x < y) ? (x) : (y)
请问 MIN(3, 5) > 4吗
|