POJ 1009 Edge Detection（一）

花了一晚上的时间才弄出来的程序居然 OutOfMemery 了，悲催。

应该是想法错了，此题不应该全局遍历的，耗时且对大数据量来说又不实际。

在问题的讨论区有人提到了一种思路，当添加一个数时会影响八个数。那么使用添加做驱动不断的修正数值是否会好些呢，又或者有其他的规律我没看到。今天就先到这，明天继续，灭了这题。

下面是今晚的成果，可惜是 WA 的：

import java.util.Scanner;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;

public class Main {
	public void run() throws Exception {
		List<Integer> elementList;

		Scanner scan = new Scanner(System.in);

		int col = scan.nextInt();
		scan.nextLine(); // get CR

		while (col != 0) {
			elementList = new LinkedList<Integer>();

			// get value and number of the value
			int value = scan.nextInt();
			int num = scan.nextInt();
			scan.nextLine(); // get CR

			while (value != 0 && num != 0) {
				for (int i = 0; i < num; i++) {
					elementList.add(value);
				}

				// get value and number of the value
				value = scan.nextInt();
				num = scan.nextInt();
				scan.nextLine(); // get CR
			}

			// create Matrix
			Matrix matrix = new Matrix(col, elementList);
			int [][] ret = matrix.getTarget();
			/* test code
			for (int i = 0; i < ret.length; i++) {
				for (int j = 0; j < col; j++) {
					System.out.println("test:ret[" + i + "][" + j + "]:" + ret[i][j]);
				}
			}*/
			Matrix.printRLE(ret);

			col = scan.nextInt();
			scan.nextLine(); // get CR
		}

	}

	public static void main(String[] args) {
		Main m = new Main();
		try {
			m.run();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}

class Matrix {
	private int[][] original;
	private int[][] target;

	/**
	 * Initialize array original.
	 */
	public Matrix(int col, List<Integer> elementList) {
		if ((elementList.size() % col) != 0) {
			throw new IllegalArgumentException("Error input data");
		}
		
		int row = elementList.size() / col;
		original = new int[row][col];
		target = new int[row][col];

		// prepare original array.
		Iterator<Integer> iter = elementList.iterator();
		int n = 0; // use to count the number of columns
		while (iter.hasNext()) {
			original[n/col][n%col] = iter.next();
			n++;
		}

		// prepare target array.
		calc(row, col);
	}

	public void calc(int row, int col) {
		for (int r = 0; r < row; r++) {
			for (int c = 0; c < col; c++) {
				if (r - 1 > 0 && c + 1 < col) {
					int v = original[r-1][c+1];
					int detal = Math.abs(original[r][c] - v);
					if (detal > target[r][c]) {
						target[r][c] = detal;
					}
					if (detal > target[r-1][c+1]) {
						target[r-1][c+1] = detal;
					}
				}
				if (c + 1< col) {
					int v = original[r][c+1];
					int detal = Math.abs(original[r][c] - v);
					if (detal > target[r][c]) {
						target[r][c] = detal;
					}
					if (detal > target[r][c+1]) {
						target[r][c+1] = detal;
					}
				}
				if (r + 1 < row && c + 1 < col) {
					int v = original[r+1][c+1];
					int detal = Math.abs(original[r][c] - v);
					if (detal > target[r][c]) {
						target[r][c] = detal;
					}
					if (detal > target[r+1][c+1]) {
						target[r+1][c+1] = detal;
					}
				}
				if (r + 1 < row) {
					int v = original[r+1][c];
					int detal = Math.abs(original[r][c] - v);
					if (detal > target[r][c]) {
						target[r][c] = detal;
					}
					if (detal > target[r+1][c]) {
						target[r+1][c] = detal;
					}
				}
				if (r + 1 > row && c - 1 > 0) {
					int v = original[r+1][c-1];
					int detal = Math.abs(original[r][c] - v);
					if (detal > target[r][c]) {
						target[r][c] = detal;
					}
					if (detal > target[r+1][c-1]) {
						target[r+1][c-1] = detal;
					}
				}
			}
		}
	}

	public static void printRLE(int[][] array) {
		int old = array[0][0];
		int count = 0;
		for (int i = 0; i < array.length; i++) {
			for (int j = 0; j < array[i].length; j++) {
				int newOne = array[i][j];
				if (old != newOne) {
					System.out.println(old + " " + count);
					old = newOne;
					count = 1;
				} else {
					count++;
				}
			}
		}

	}

	public int[][] getOriginal() {
		return original;
	}

	public int[][] getTarget() {
		return target;
	}
}