POJ1009-Edge Detection

来源:转载

转载请注明出处:優YoU   http://user.qzone.qq.com/289065406/blog/1311227000

大致题意:

某种卫星使用一种叫做“run length encoding”的方式来储存大尺寸图片,

有一种简单的 edge detection 算法 是将 图像中的每一个点的值与他周围的八个点相减,然后记录下绝对值最大的,上面的右图是左图经过这种算法转换之后的结果。

现在你的任务就是实现这个算法,输入的图片是以 run length encoding 的形式表示的,同时也要求转换后的图片也以 run length encoding 的形式表示。

 

解题思路:

非常令人纠结的模拟题,

由于图片宽度可能为10^9,因此不能开数组,会MLE

又因为像素点很多,不能直接暴力,会TLE

 

突破点在于Input的pair,pair上限只有1000,数据量是最少的,因此只能利用这点去解题。

要利用pair,就必须懂得“跳跃式编码”,就是说只在像素发生变化的位置进行编码,而像素没有变化的位置则其编码值与其左边的像素一致。

 

我只说解题方法,不给证明了。

先给所有像素点pix顺序标号pos,从1开始,以这个标号pos作为该像素点pix的索引

利用pos去模拟pix在二维图片的坐标row=(pos-1)/width,col=(pos-1)%width

这样就无需定义二维数组,仅仅虚构了一个二维数组,就解决了空间溢出MLE的问题

 

接下来在 像素发生变化的位置(下面称为“边界”)的地方 编码

边界位置其实就是每对pair的个数决定的,对边界位置及其周遭共9个像素点编码,把编码结果及对应的索引pos都存放在OutMap,编码方法就是题目给出的算法

最后把OutMap中的编码值根据其索引值进行升序排序,依次读取OutMap中的编码值,当编码值code发生变化时,则用 变化后的编码索引 减去 变化前的编码索引,就是code在OutMap中出现的次数。

 

 

Source修正:

Mid-Central USA 2000

http://mcpc.cigas.net/archives/2000/browse.html

 

 1 //Memory Time 
2 //332K 32MS
3
4 #include<iostream>
5 #include<cmath>
6 #include<algorithm>
7 using namespace std;
8
9 const int size=1000; //每幅图片的pair上限
10 int width; //Map的宽
11 int total=0; //像素点总个数
12
13 typedef class OutMapPix
14 {
15 public:
16 int pos; //OutMap中每个像素点的顺序位置,pos从1开始
17 int code; //OutMap中每个像素点对应InMap的编码
18 }Pix;
19
20 int InMapPair[size][2]; //InMapPair[][0]为像素值,InMapPair[][1]为InMapPair[][0]连续出现的个数
21 Pix OutMap[size*8]; //每个pix都依赖其周围的8个点编码
22
23 int cmp(const void* a,const void* b); //快排比较规则
24 int GetValue(int pos); //返回第pos个像素点的像素值
25 int GetCode(int pos); //返回第pos个像素点的编码
26
27 int main(int k)
28 {
29 while(cin>>width && width)
30 {
31 int pairv,pairt;
32 k=total=0;
33 while(cin>>pairv>>pairt && pairt)
34 {
35 InMapPair[k][0]=pairv;
36 InMapPair[k++][1]=pairt;
37 total+=pairt;
38 }
39 int PairNum=k; //pair的个数
40
41 cout<<width<<endl;
42
43 int pos=1; //当前处理的像素点的位置
44 k=0; //OutMap[]指针
45 for(int p=0;p<=PairNum;p++)
46 {
47 int row=(pos-1)/width; //得到pos在二维图对应的坐标
48 int col=(pos-1)%width;
49
50 for(int i=row-1;i<=row+1;i++) //枚举(row,col)周围及其自身共9个点(x,y)
51 for(int j=col-1;j<=col+1;j++)
52 {
53 int tpos=i*width+j; //得到(x,y)的顺序位置
54
55 if(i<0 || j<0 || j>=width || tpos>=total)
56 continue;
57
58 OutMap[k].pos=tpos+1;
59 OutMap[k++].code=GetCode(tpos+1); //对发生变化的像素点的附近8个点编码
60 }
61
62 pos+=InMapPair[p][1]; //跳跃,确定下一个像素发生变化的点的位置
63 }
64
65 qsort(OutMap,k,sizeof(Pix),cmp); //对OutMap根据顺序位置
66
67 /*OutPut*/
68
69 Pix temp=OutMap[0];
70 for(int i=0;i<k;i++)
71 {
72 if(temp.code==OutMap[i].code)
73 continue;
74 cout<<temp.code<<' '<<OutMap[i].pos-temp.pos<<endl;
75 temp=OutMap[i];
76 }
77 cout<<temp.code<<' '<<total-temp.pos+1<<endl;
78 cout<<"0 0"<<endl;
79
80 }
81 cout<<0<<endl;
82
83 return 0;
84 }
85
86
87 /*快排比较规则*/
88 int cmp(const void* a,const void* b)
89 {
90 Pix* x=(Pix*)a;
91 Pix* y=(Pix*)b;
92 return x->pos - y->pos;
93 }
94
95 /*返回第pos个像素点的像素值*/
96 int GetValue(int pos)
97 {
98 int i=0,p=0;
99 while(p<pos)
100 p+=InMapPair[i++][1];
101
102 return InMapPair[i-1][0];
103 }
104
105 /*返回第pos个像素点的编码*/
106 int GetCode(int pos)
107 {
108 int code=GetValue(pos);
109 int MaxAbs=0;
110
111 int row=(pos-1)/width;
112 int col=(pos-1)%width;
113
114 for(int i=row-1;i<=row+1;i++)
115 for(int j=col-1;j<=col+1;j++)
116 {
117 int tpos=i*width+j;
118
119 if(i<0 || j<0 || j>=width || tpos>=total || tpos==pos-1) //tpos==pos-1为中心的像素点,即当前待编码的点
120 continue;
121
122 int tcode=GetValue(tpos+1);
123
124 if(MaxAbs<abs(tcode-code)) //注意取绝对值
125 MaxAbs=abs(tcode-code);
126 }
127
128 return MaxAbs;
129 }

Sample Input

3255 110 1255 210 1255 210 1255 10 01035 500000000200 5000000000 0715 4100 1525 2175 225 5175 225 50 084 81 12 14 18 16 14 12 10 10 081 12 14 18 16 14 12 10 11 12 14 18 16 14 12 10 10 081 12 14 18 16 14 12 10 10 0515 12100 315 1100 415 2100 30 03010 4120 4115 4130 4125 410 50 01255 20 0104 206 200 014 10000000000 010000000004 10000000000 03010 4120 4115 4130 4125 410 50 081 12 14 18 16 14 12 10 11 12 14 18 16 14 12 10 11 12 14 18 16 14 12 10 10 081 12 14 18 16 14 12 10 14 80 084 81 12 14 18 16 14 12 10 15 80 0530 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 1130 1120 1110 1120 110 00

Sample Output

3245 90 0100 499999990165 200 4999999900 0785 50 285 575 10150 275 30 2150 20 40 083 24 32 14 23 12 14 22 34 10 081 12 14 22 41 12 14 22 40 081 12 14 22 40 050 685 120 285 30 20 0300 1010 625 2015 625 2025 65 150 925 60 010 20 0100 102 200 100 010 10000000000 010000000000 10000000000 0300 1010 625 2015 625 2025 65 150 925 60 081 12 14 22 41 12 14 22 41 12 14 22 40 083 12 14 22 34 13 24 32 14 20 083 24 32 14 33 14 22 23 15 14 23 45 20 050 510 109900 50 00
我的所有ACM解题报告:http://user.qzone.qq.com/289065406/blog/1301632863 || 我的CSDN:http://hi.csdn.net/invite.php?u=10114444&c=57929f66dd919f2b || 我的新浪微博:http://weibo.com/lyy289065406 || 我的腾讯微博:http://t.qq.com/lyy289065406 || 我的QQ空间:http://user.qzone.qq.com/289065406 || 我的百度空间:http://hi.baidu.com/you289065406/home || 我的金山网盘:http://www.kuaipan.cn/register/?invite=evpga1


分享给朋友:
您可能感兴趣的文章:
随机阅读: