poj 1009 Edge Detection
Edge Detection
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 25131 | Accepted: 6026 |
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.
Sample Input
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
Sample Output
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
Hint
A brute force solution that attempts to compute an output value for every individual pixel will likely fail due to space or time constraints.
边缘检测
描述
IONU卫星成像公司使用行程长度编码记录和存储非常大的图像。你要编写一个程序，读取压缩图像，找到图像中的边缘，如下所述，并输出检测到的边缘的另一个压缩图像。
一种简单的边缘检测算法将输出像素的值设置为该像素与输入图像中所有周围像素的差值的最大绝对值。考虑下面的输入图像:
输出图像左上角像素为|15 ~ 15|、|15 ~ 100|、|15 ~ 100|的最大值，即85。第二列第四行像素计算为|175-100|，|175-100|，|175-100|，|175-175|，| 175-25|，|175-175|，|175-175|，|175-25|的最大值，即150。
图像包含2到1,000,000,000(109)像素。所有图像都使用行程长度编码(RLE)进行编码。这是一个对的序列，包含像素值(0-255)和运行长度(1-109)。输入图像最多有1000个这样的对。连续对具有不同的像素值。图像中的所有线条都包含相同数量的像素。
输入
输入由一个或多个图像的信息组成。每个图像都以每条图像线的宽度(以像素为单位)开始。后面是RLE对，每行一对。带有0 0的行表示该图像的数据结束。图像宽度为0表示没有更多的图像需要处理。示例输入中的第一个图像编码了上面的5x7输入图像。
输出
输出的是一系列边缘检测图像，格式与输入图像相同，但RLE对可能超过1000对。
Sample Input
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
Sample Output
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
提示
试图为每个像素计算输出值的蛮力解决方案可能会由于空间或时间限制而失败。
首先，暴力必挂，这是题目的善意提醒。
于是，一直在想不暴力的各种判断计算方法，关于各种跳跃移动，后来都无奈想用STL。原谅我的蒟蒻。
再然后就思维混乱了。于是看网上各位大神的解题报告。很神奇的一个搞法。瞬间被震惊。发现了一个道理，有时候从这个角度搞不通的时候，换一个更直接的角度往往一下就搞通了。是的。
首先可以看出来，这个最终的答案中，肯定会有某些连续段，答案是不变的，这些连续段又和原图有关。我自己的思路就是，先找出在原图的某一连续段中，答案值可能改变的几个像素（做标记），再一次次跳跃到这几个像素中计算它们的答案值，但是问题就是，怎么样的像素才是需要计算的像素。
如图的一个map：
第一个x显然是需要标记的。然后，可以直接跳跃到第4个x，因为此时它的周围多了一个z，答案可能改变，而第二、三个x显然答案和第一个是一样的。再然后，y的第一个也肯定要标记，因为主体变了。然后到了坐标为(2,3)的y，它需要标记是因为它的周围多了一个m。于是以此类推完成。虽然这个搞法看似可以，但这么多的细节要考虑，况且格子数是10^9，以我的水平注定挂。该怎么办呢。在看了各位大神的题解之后，发现其实我只要把需要标记的格子标记出来，并且把每一连续段的分段画出来，就可以发现很神奇的东西：
紫色标注的都是要标记的格子，红色边框的代表这一个连续段的起始格。我们可以发现，每个连续段的起始格，都是要标记的格子，同时，每个要标记的格子，都是一个连续段起始格的周围8个格子中的一个。所以，改进的搞法就很清楚了：只需要一个个枚举每个连续段的起始格，并计算它和它四周8个格子的答案值，最后统计答案的时候按照位置先后排序，答案中相同的连续段就合并。因为最多只有1000个连续段，所以不管是时间还是空间都不会超。
代码：
#include
#include
#include
#include
#define size 1005
using namespace std;
struct pix
{
int pos; //表示答案中这个点的位置
int code; //这个点上的答案值
}outmap[size*8];
int inmap[size][2];//inmap[][0]表示这个连续段的数值，inmap[][1]表示这个连续段的长度
int width,cntp,tot;
int cmp(pix x,pix y)//排序比较函数，最后以pos升序排序
{
return x.pos}
int getnum(int pos)//返回原图中pos位置上的数值
{
int p=0,i=0;
while (p p+=inmap[i++][1];
return inmap[i-1][0];
}
int getcode(int pos)//计算pos位置上的答案
{
int num=getnum(pos),ret=0;
int row=(pos-1)/width;//关于row和col的原理主程序中有
int col=(pos-1)%width;
for (int i=row-1;i<=row+1;i++)
for (int j=col-1;j<=col+1;j++)
{
int tpos=i*width+j;
if (i<0||j<0||j>=width||tpos>=tot || tpos==pos-1)
continue;//这里计算差的绝对值时要排除pos自己
int tmp=getnum(tpos+1);
if (abs(tmp-num)>ret)ret=abs(tmp-num);//更新ret
}
return ret;
}
int main()
{
while (scanf("%d",&width)&& width>0)
{
int num,len;
cntp=tot=0;//必须得每次都赋0
while (scanf("%d%d",&num,&len)&& len>0)
{
inmap[cntp][0]=num;
inmap[cntp++][1]=len;
tot+=len;//tot是map中像素的个数
}
printf("%d\n",width);//按照同样格式输出
int pos=1,k=0;//pos从1开始标号
for (int p=0;p<=cntp;p++)//枚举每一个连续段
{
int row=(pos-1)/width;
int col=(pos-1)%width;
for (int i=row-1;i<=row+1;i++)
for (int j=col-1;j<=col+1;j++)
{
int tpos=i*width+j;//这里算出来的tpos其实是tpos的标号减一
if (i<0 || j<0 || j>=width || tpos>=tot)
continue;//tpos在map的外面了
outmap[k].pos=tpos+1;
outmap[k++].code=getcode(tpos+1);//答案存入outmap
}
pos+=inmap[p][1];//跳跃到下一个连续段的起始格
}
sort(outmap,outmap+k,cmp);
pix tmp=outmap[0];
for (int i=0;i {
if (outmap[i].code==tmp.code) //表明连续，则跳过不输出
continue;
printf("%d %d\n",tmp.code,outmap[i].pos-tmp.pos);
tmp=outmap[i];
}
printf("%d %d\n",tmp.code,tot-tmp.pos+1);//最后一部分
printf("0 0\n");//按照格式输出
}
printf("0\n");//格式
return 0;
}