[cpp]
<span style="line-height: 1.1em; font-family: 'Lucida Grande', Verdana, 'Bitstream Vera Sans', Arial, sans-serif; ">從第一個點開始，依次算出與當前點的邊緣差值相同的點的個數，如果某個重復次數大於 w * 5那麼一定會有一連續的整行為0的輸出。故此處可特判一下。然後在輸出的過程中注意如果可以和前面的合並的就合並。判斷的話主要判斷某點正上方和正下方的點所能夠達到最遠的距離（即像素發生變化的地方）。超過了本行時變設為w；最後去3列的最小值。行數為當前點的行。具體見代碼。</span>
描述
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 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 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.
樣例輸入
7
15 4
100 15
25 2
175 2
25 5
175 2
25 5
0 0
10
35 500000000
200 500000000
0 0
3
255 1
10 1
255 2
10 1
255 2
10 1
255 1
0 0
0
樣例輸出
7
85 5
0 2
85 5
75 10
150 2
75 3
0 2
150 2
0 4
0 0
10
0 499999990
165 20
0 499999990
0 0
3
245 9
0 0
0
[cpp]
# include <stdio.h>
# include <stdlib.h>
# include <memory.h>
# define min(a,b) (a) < (b) ? (a) : (b)
int pix[1001], begin[1001], sum;
int ans[2012];
int cha[2012];
int cnt;
int w;
int *around;
int getPix (int nd) {
int p = 0, r = cnt + 1;
if (begin[r] <= nd) return r;
while (p + 1 < r) {
int mid = (p + r) >> 1;
if (begin[r] == nd) return r;
if (begin[mid] > nd) {
r = mid;
}
else if (begin[mid] < nd) {
p = mid;
}
else return mid;
}
return p;
}
int abs(int a) {
return a > 0 ? a : -a;
}
int getMax (int nd) {
int max = 0;
int l = 0, r = 8;
if (nd % w == 0) r = 5;
if (nd % w == 1) l = 3;
if (w == 1) {r = 5; l = 3;}
for (int i = l; i < r; ++ i) {
int t = nd + around[i];
if (t <= sum && t > 0) {
int m = pix[getPix(nd)];
int c = abs(pix[getPix(t)] - m);
max = max > c ? max : c;
}
}
return max;
}
int findEnd (int nd) {
int index = getPix (nd);
return begin[index + 1] - 1;
}
int getRow(int nd) {
return (nd - 1) / w + 1;
}
int getCol(int nd) {
return nd - (getRow(nd) - 1) * w;
}
int getPos (int row, int col) {
return w * (row - 1) + col;
}
int next (int nd) {
int a, b, c;
a = b = c = findEnd(nd);
if (nd - w > 0)
b = findEnd(nd - w);
if (nd + w <= sum)
c = findEnd(nd + w);
int row_a = getRow(a), col_a = getCol(a);
int row_b = getRow(b), col_b = getCol(b);
int row_c = getRow(c), col_c = getCol(c);
int row_nd = getRow(nd);// col_nd = getCol(nd);
if (a == b && b == c && nd - w > 0 && nd + w <= sum && row_c - 3 >= row_nd) return getPos(row_c - 2, w);
if (row_b >= row_nd) col_b = w;
if (row_c > row_nd + 1) col_c = w;
if (row_a > row_nd) col_a = w;
int col_min = min(col_a, min(col_b, col_c));
return getPos(row_nd, col_min);
}
int main () {
while ( (scanf("%d", &w), w) ) {
int a[] = {-1, -1 + w, -1 - w, w, -w, 1 + w, 1, 1 - w};
around = a;
int x, y;
cnt = -1;
sum = 0;
begin[0] = 1;
memset (cha, 0, sizeof(cha));
memset (ans, 0, sizeof(ans));
while ( (scanf ("%d %d", &x, &y), x + y ) ) {
pix[++ cnt] = x;
begin[cnt + 1] = begin[cnt] + y;
sum += y;
}
int anscnt = 0;
/*
for (int i = 1; i <= sum; ++ i) {
printf ("%d ", getMax(i));
if (i % w == 0) printf ("\n");
}
*/
int p = 2;
cha[0] = getMax(1);
ans[0] = 1;
while (p <= sum) {
int mp = getMax(p);
int tmp = next(p);
if (mp == cha[anscnt]) {
ans[anscnt] += tmp - p + 1;
}
else {
cha[++ anscnt] = mp;
ans[anscnt] = tmp - p + 1;
}
if (getMax(tmp) != getMax(tmp - 1) && (tmp - p) >=1 ) {
-- ans[anscnt];
cha [++ anscnt] = getMax(tmp);
ans[anscnt] = 1;
} www.2cto.com
p = tmp + 1;
if(p > sum) break;
if (getMax(p) == cha[anscnt]) ++ ans[anscnt];
else {
cha[++ anscnt] = getMax(p);
ans[anscnt] = 1;
}
++ p;
}
printf ("%d\n", w);
for (int i = 0; i <= anscnt; ++ i) {
printf ("%d %d\n", cha[i], ans[i]);
}
printf ("0 0\n");
}
printf ("0\n");
return 0;
}
