北大食堂的故事 — Windows Live

北大食堂的故事 — Windows Live

Google后花园 | Google Garden: 让Blogger首页只显示帖子摘要的技巧

Google后花园 | Google Garden: 让Blogger首页只显示帖子摘要的技巧

POJ 1009 Edge Detection 解题报告

题意

• 输入：一种叫RLE格式的图片，该格式为两列数据，第一列代表像素值，第二列代表该像素值连续出现的次数。数据不超过1000行，相邻两行的第一列不等；第二列的值可以是1G的量级。
• 输出：采用RLE格式输出，第一列是，某个点的像素值和它周围8个点的最大差值；第二列代表该值连续出现的次数。

思路

• 显然不能用矩阵把输入图片“画”出来再计算，对于1G的量级，时间和空间代价都会很大。
• 假设从左到右逐行读取图片像素：当知道某个点右下角的像素值时，该点的边缘差值就可以算出来了。假设图片宽度为n，那么从第n+1个点开始，就可以逐个计算其左上角点的边缘差值了。为该差值计数，当前差值如果不等于之前的值，那么把之前的值和计数输出，重新开始计数。
• 考虑第i个点（i>n+1，从左到右，逐行计数），其左上角的点c是i-n-1，点c从左开始，顺时针方向的8个点分别是c-n-1，c-n-1，c-n，c-n+1，c+1，c+n+1，c+n，c+n-1。只要求得这8个点的像素值，c点的边缘差值就知道了。

数据结构

• 输入数据可以保存下来，用两个数组，i_val保存像素值，i_num保存该像素值的右边界，用第二个数组，很容易从某个index开始，向前搜索点c对应的idx，从而得到c的像素值。
  

• 输出结果不需要存下来，逐行输出即可。

优化

• 如果逐点计算，肯定会超时。考虑两种情况：行跳跃和列跳跃。
• 行内跳跃：这是考虑n非常大的情况。假设点c的LEFTUP和RIGHTUP的idx相等，表示其上方区域是成块的；同理，如果c的上中下三行各自成块，那么c附近的点边缘差值都一致，可以不用计算，直接跳跃；注意跳跃的边界：最多跳到该行最后一个点，因为下一行的UP值位置；最多跳到该块的右数第二个点，因为右数第一个点的右列未知。
• 列间跳跃：这是考虑n比较小，但是RLE的length值非常大的情况。跳跃的条件是：块的上下方各留一行。

Keynote

• 前n个点可以直接跳过，不用再循环中计算；
• y代表当前点在图片中的列标。y=1时，开始考虑列间跳跃；
• y>1时，计算其左上角点的边缘差值，同时考虑行内跳跃；
• y==n时，还需要计算其上方点的边缘差值。
• 对最后一行，逐个计算点，同时考虑行内跳跃。

心得

• 第一次做的时候，觉得时间可以再优化，因为：对于每个点，只用计算4个值即可，另外4个值可以从它相邻的点那儿得到；如果能这样优化，计算量会减少，但是：需要记录3行的点的情况，不适用于n非常大的输入。该做法以WA告终。
• 这道题思路不难，但是各种边界值非常难搞定，我反复debug了两天，最后才AC。
• 练手不错，不过解题速度太慢了，memory还是大。
  

Problem: 1009		User: chenxr
Memory: 456K		Time: 0MS
Language: G++		Result: Accepted