首页 > 专题系列 > Java解POJ > POJ 1009 Edge Detection [解题报告] Java
2013
11-08

POJ 1009 Edge Detection [解题报告] Java

Edge Detection

问题描述 :

IONU Satellite Imaging, Inc. records and stores very large http://poj.org/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 http://poj.org/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 http://poj.org/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 5×7 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.

解题代码:

//* @author popop0p0popo
import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args){
   Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
   int n,dtf,m,mn,cp,cpl;
   int[][] dt;
   while (true){
    n=scanner.nextInt();
    if (n==0){
	break;
    }
	System.out.println(n);
	dt=new int[2][10000];
	dtf=0;
	while (true){
		dt[0][dtf]=scanner.nextInt();
		dt[1][dtf]=scanner.nextInt();
		if (dt[0][dtf]==0&&dt[1][dtf]==0){
			break;
		}
		dtf++;
	}
	mn=0;
	for (int i=0;i< 10000 ;i++ ){
		if (dt[1][i]==0){
			break;
		}
		mn=mn+dt[1][i];
	}
	m=mn/n;
	cp=getM(dt,0,0,m,n);
	cpl=0;
	int flag=0;
	for (int i=0;i< m ;i++ ){
	  if (dt[1][getV(dt,i,0,n)]-flag>4*n&&flag>=n){
	  int t=dt[1][getV(dt,i,0,n)]-flag-(dt[1][getV(dt,i,0,n)]-flag)%n-n;
		if (cp==0){
	         cpl=cpl+t;
		}
		else{
		 System.out.println(cp+" "+cpl);
		 cp=0;
		 cpl=t;
		}
		flag=flag+t;
		i=i+t/n;
		}
	     for (int j=0;j< n ;j++ ){
		if (getM(dt,i,j,m,n)==cp){
		 cpl++;
	       }
		else{
		 System.out.println(cp+" "+cpl);
		 cp=getM(dt,i,j,m,n);
		 cpl=1;
		}
		flag++;
		 if (flag>=dt[1][getV(dt,i,j,n)]){
		  flag=0;
		}
		if (getE(dt,i,j,n,m)>=3&&j+getE(dt,i,j,n,m)-2< n){
		 if (cp==getM(dt,i,j+1,m,n)){
			cpl=cpl+getE(dt,i,j,n,m)-2;
		}
		else{
			System.out.println(cp+" "+cpl);
			cp=getM(dt,i,j+1,m,n);
			cpl=getE(dt,i,j,n,m)-2;
		}
			flag=flag+getE(dt,i,j,n,m)-2;
			j=j+getE(dt,i,j,n,m)-2;
		}
		}
		}
			System.out.println(cp+" "+cpl);
			System.out.println("0 0");
		}
		System.out.println(0);
	}

	public static int getE(int[][] dt,int ii,int jj,int n,int m){
		if (m==1){
			return getVA(dt,ii,jj,n);
		}
		else if (m==2||ii==0){
			return getMin(getVA(dt,0,jj,n),getVA(dt,1,jj,n));
		}
		else if (ii==m-1){
			return getMin(getVA(dt,m-1,jj,n),getVA(dt,m-2,jj,n));
		}
		else{
return getMin(getMin(getVA(dt,ii,jj,n),getVA(dt,ii+1,jj,n)),getMin(getVA(dt,ii,jj,n),getVA(dt,ii-1,jj,n)));
		}
	}

	public static int getMin(int a,int b){
		if (a< b){
			return a;
		}
		return b;
	}

public static int getM(int[][] dt,int ii,int jj,int m,int n){
  int max=0;
  for (int i=-1;i< 2 ;i++ ){
   for (int j=-1;j< 2;j++ ){
    if (i==0&&j==0){
      continue;
    }
    else if (jj==0&&j==-1){
      continue;
    }
    else if (jj==(n-1)&&j==1){
      continue;
    }
    else if (ii==0&&i==-1){
      continue;
    }
    else if (ii==(m-1)&&i==1){
      continue;
    }
    else{
      if (Math.abs(dt[0][getV(dt,ii,jj,n)]-dt[0][getV(dt,ii+i,jj+j,n)])>max){
	max=Math.abs(dt[0][getV(dt,ii,jj,n)]-dt[0][getV(dt,ii+i,jj+j,n)]);
      }
    }
  }
 }
    return max;
}

   public static int getV(int[][] dt,int ii,int jj,int n){
    int t=ii*n+jj+1;
    int total=0;
    int flag=0;
    while (t>total){
      total=total+dt[1][flag];
      flag++;
    }
    return flag-1;
  }

  public static int getVA(int[][] dt,int ii,int jj,int n){
		int t=ii*n+jj+1;
		int total=0;
		int flag=0;
		while (t>total){
			total=total+dt[1][flag];
			flag++;
		}
		return total-t;
	}
}

  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  3. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3