outline.java

轮廓问题的源代码

package outline;

import java.util.*;
import java.io.*;

public class Outline {
	static String infile = "data1.dat";
	static String outfile = "result1.dat";
	
	private static ArrayList<Integer> makeArray (String str){
		ArrayList<Integer> number = new ArrayList<Integer>();
		int first = str.indexOf(" ");
		int second = str.indexOf(" ",first+1);
		number.add(0);
		number.add(Integer.valueOf(str.substring(0,first)));
		number.add(Integer.valueOf(str.substring(first+1,second)));
		number.add(Integer.valueOf(str.substring(second+1,str.length())));
		number.add(0);
		return number;
	}
	
	private static ArrayList<Integer> addIntoArray 
		(int hight1, int location1,int hight2,int location2
				, int model, ArrayList<Integer> result) {
		int last = result.get(result.size()-1);
		if (result.size()%2==0 && model == 1){
			if (location1 != last){
				result.add(hight1);
				result.add(location1);
			}
		}
		else if (result.size()%2 == 0 && model == 0){
			if (location1 == last){
				result.add(hight1);
			}
			else {
				result.add(hight2);
				result.add(location1);
				result.add(hight1);
			}
		}
		else if (result.size()%2 == 1 && model == 0){
			if (hight1 != last) {
				result.add(location1);
				result.add(hight1);
			}
		}
		else {
			if (hight1 == last){
				result.add(location1);
			}
			else {
				result.add(location2);
				result.add(hight1);
				result.add(location1);
			}
		}
		return result;
	}
	
	private static ArrayList<Integer> outlineProblem (int low, int high, RandomAccessFile ol)throws IOException{		
		if (high == low) {
			ArrayList<Integer> a = new ArrayList<Integer>();
			String line = ol.readLine();
			a = makeArray(line);
			return a;
		}
		else {
			ArrayList<Integer> a = new ArrayList<Integer>();
			ArrayList<Integer> b = new ArrayList<Integer>();
			ArrayList<Integer> result = new ArrayList<Integer>();
			int middle = (high + low)/2;
			a = outlineProblem(low, middle, ol);
			b = outlineProblem(middle+1, high, ol);	
			result.add(0);
			
			int m = 1,n=1;
			while (m<a.size()&&n<b.size()) {
				if(a.get(m) < b.get(n)){
					if (a.get(m+1)< b.get(n-1)){
						result=addIntoArray(b.get(n-1),b.get(n),a.get(m+1),a.get(m),1,result);
					}
					else {
						result=addIntoArray(a.get(m+1),a.get(m),b.get(n-1),b.get(n),0,result);
					}
					m = m +2;
				}
				else if (a.get(m) > b.get(n)) {
					if (a.get(m-1)> b.get(n+1)){
						result=addIntoArray(a.get(m-1),a.get(m),b.get(n+1),b.get(n),1,result);
					}
					else {
						result=addIntoArray(b.get(n+1),b.get(n),a.get(m-1),a.get(m),0,result);
					}
					n=n+2;
				}
				else {
					result=addIntoArray(Math.max(b.get(n+1),a.get(m+1)),b.get(n),Math.max(b.get(n-1),a.get(m-1)),a.get(m),0,result);
					m=m+2;
					n=n+2;
				}
			}
			if (m<a.size() && result.size()%2== 0) {
				for (int i = m +1; i<a.size();i++){
					result.add(a.get(i));
				}
			}
			else if (m<a.size() && result.size()%2== 1){
				for (int i = m; i<a.size();i++){
					result.add(a.get(i));
				}
			}
			else if (n<b.size() && result.size()%2== 1){
				for (int i = n; i<b.size();i++){
					result.add(b.get(i));
				}
			}
			else {
				for (int i = n +1; i<b.size();i++){
					result.add(b.get(i));
				}
			}
			return result;
		}
		
	}
	
	public static void main(String[] args) throws IOException{
		try {
			RandomAccessFile in = new RandomAccessFile(infile, "r");
			PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(outfile)));
			int length = Integer.valueOf(in.readLine());
			ArrayList<Integer> result = outlineProblem (1,length,in);
			for (int i = 1; i < result.size()-1; i++){
				out.println(result.get(i));
			}
			in.close();
			out.close();
		}
		catch ( java.io.FileNotFoundException e){
			System.out.println("Can't find file: \"data1.dat\"");
		}
		catch( Exception e){
			System.out.println("ERROR! wrong file format");
		}
	}
}