1009

总时间限制:

1000ms

内存限制:

65536kB

描述

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 (10⁹) 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-10⁹). 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

提示

A brute force solution that attempts to compute an output value for every individual pixel will likely fail due to space or time constraints.

最近比较累,有时间又去搞web去了,做这种题我认为最打的 收获就是增进我对语言的了解和使用程度。

这道题让很多人痛心疾首啊！无奈啊！

 

 

解决方案一： G++

 

 

#include<stdio.h>
#include<cstdlib>
typedef struct Pixel{
  int index ;//位置
  int code ;//值
} Pl;
int IN[1000][2] ;//存储输入的数据
Pl OUT[8000] ;//存储要输出的数据
int getCode(int n) ;
int enCode(int n,int width,int total) ;
void sort(Pl* list,int n) ;
int main()
{
  int width,i,j,total,line,n,k,m,row,col,t;
  Pl px ;
  while(scanf("%d",&width)!= EOF)//width为0跳出
  {
      if(width==0) break ;

/**
输入
*/
   i = total = 0 ;
   scanf("%d%d",&IN[i][0],&IN[i][1]) ;
   while(IN[i][0]!=0 || IN[i][1]!=0)
    {
        total+=IN[i][1] ;//计算总像素点
        i++ ;
        scanf("%d%d",&IN[i][0],&IN[i][1]) ;
    }

    printf("%d\n",width) ;//输出宽度
/**
计算
*/
    line = i ;
    n = 1 ;
    k = 0 ;
   for(m=0;m<=line;m++)//
   {
      row = (n-1) / width ;//求得元素所在的行
      col = (n-1) % width ;//求得元素所在的列
/**
通过遍历获得元素周围的8个元素
*/
   for(i=row-1;i<=row+1;i++){
    for(j=col-1;j<=col+1;j++){
      t = i * width + j ; //t为元素所在的位置
      if(i<0 || j<0 || t>total-1 || j>width-1) //不符合条件的跳过
         {  continue ;  }
     OUT[k].index = t + 1;
     OUT[k++].code = enCode(t+1,width,total) ;
    }
   }
   n += IN[m][1] ;
}
/**
输出
*/
sort(OUT,k) ;
  px = OUT[0] ;
  for(i=0;i<k;i++)
  {
    if(OUT[i].code==px.code)
        continue ;

  printf("%d %d\n",px.code,OUT[i].index-px.index) ;
    px = OUT[i] ;
  }
printf("%d %d\n", px.code, total - px.index + 1);
  printf("0 0\n");
  }
  printf("0\n");
  return 0 ;
}
/**
返回第n个元素的编码，n从1开始
*/
int getCode(int n)
{
    int t,i ;
    i = t = 0 ;
   while(t<n)
   {
       t += IN[i++][1] ;
   }
   return IN[i-1][0] ;
}
/**
对第n个元素进行编码，n从1开始
*/
int enCode(int n,int width,int total)
{
    int i,j,t,code,result,row,col;
    code = getCode(n) ;//得到该元素编码
    row = (n-1) / width ;
    col = (n-1) % width ;
    result = 0 ; //记录绝对值最大的数
    for(i=row-1;i<=row+1;i++){
        for(j=col-1;j<=col+1;j++){
            t = i*width + j ;
            if(i<0||j<0||t>total-1||j>width-1||t==n-1)
                continue ;

            if(abs(getCode(t+1)-code)>result)
             result = abs(getCode(t+1)-code) ;
            }
          }
        return result ;
}
/**
排序
*/
void sort(Pl *list,int n)
{
    Pl tmp ;
    int i,j ;
    for(i=0;i<n;i++){
    for(j=i+1;j<n;j++){
        if(list[i].index > list[j].index)
        {
            tmp = list[i] ;
            list[i] = list[j] ;
            list[j] = tmp ;
        }
    }
    }
}

 

 

 

 

 

 

解决方案二： Java

 

 

package dsa;

import java.util.Scanner;

public class Demo11 {
  int IN[][] = new int[1000][2] ;
  Pixel OUT[] = new Pixel[8000] ;
	
public static void main(String args[])
	{
		new Demo11().test() ;
	}
public void test()
{
	int width,i,j,total,line,n,k,m,row,col,t;
	Pixel px = new Pixel() ;
	Scanner sc = new Scanner(System.in);
	while(sc.hasNext())
	{
		width = sc.nextInt() ;
		if(width==0) break ;
		i = total = 0 ;
		IN[i][0] = sc.nextInt() ;
		IN[i][1] = sc.nextInt() ;
		while(IN[i][0]!=0 || IN[i][1]!=0)
	    {
	        total+=IN[i][1] ;
	        i++ ;
	        IN[i][0] = sc.nextInt() ;
			IN[i][1] = sc.nextInt() ;
	    }
		System.out.printf("%d\n",width) ;

	    line = i ;
	    n = 1 ;
	    k = 0 ;
	   for(m=0;m<=line;m++)//
	   {
	      row = (n-1) / width ;//求得元素所在的行
	      col = (n-1) % width ;//求得元素所在的列
	/**
	通过遍历获得元素周围的8个元素
	*/
	   for(i=row-1;i<=row+1;i++){
	    for(j=col-1;j<=col+1;j++){
	      t = i * width + j ; //t为元素所在的位置
	      if(i<0 || j<0 || t>total-1 || j>width-1) //不符合条件的跳过
	         {  continue ;  }
	      OUT[k] = new Pixel() ;
	     OUT[k].index = t + 1;
	     OUT[k++].code = enCode(t+1,width,total) ;
	    }
	   }
	   n += IN[m][1] ;
	}
	   sort(OUT,k) ;
	  px = OUT[0] ;
	  for(i=0;i<k;i++)
	  {
	    if(OUT[i].code==px.code)
	        continue ;
	    
	System.out.printf("%d %d\n",px.code,OUT[i].index-px.index) ;
	 
	    px = OUT[i] ;
	  }
	  System.out.printf("%d %d\n", px.code, total - px.index + 1);
	  System.out.printf("0 0\n");
	  }
	
	System.out.printf("0\n");   
}
public int  getCode(int n)
{
	int t,i ;
    i = t = 0 ;
   while(t<n)
   {
       t += IN[i++][1] ;
   }
   return IN[i-1][0] ;
}
public int enCode(int n,int width,int total)
{

    int i,j,t,code,result,row,col;
    code = getCode(n) ;//得到该元素编码
    row = (n-1) / width ;
    col = (n-1) % width ;
    result = 0 ; //记录绝对值最大的数
    for(i=row-1;i<=row+1;i++){
        for(j=col-1;j<=col+1;j++){
            t = i*width + j ;
            if(i<0||j<0||t>total-1||j>width-1||t==n-1)
                continue ;

            if(Math.abs(getCode(t+1)-code)>result)
             result = Math.abs(getCode(t+1)-code) ;
            }
          }
        return result ;
}
public void sort(Pixel[] list,int n){
	Pixel tmp = new Pixel();
	int i,j ;
	 for(i=0;i<n-1;i++){
		    for(j=i+1;j<n;j++){
		        if(list[i].index > list[j].index)
		        {
		            tmp = list[i] ;
		            list[i] = list[j] ;
		            list[j] = tmp ;
		        }
		    }
		    }
	 
}
 class Pixel{
		int index ;
		int code  ;
	}

}

 

不知道为什么，java的过不了，答案对上了，如果有大神知道的话，请告诉我一下。