V8SORT - Sắp xếp

Tác giả: khuc_tuan

Ngôn ngữ: Java

import java.util.*;

public class Main {
	
	static Map<int[], Integer> ma;
	
	public static void main(String[] args) {
		ma = new TreeMap<int[], Integer>(new Comparator<int[]>() {
			public int compare(int[] a,int[] b) {
				if(a.length!=b.length) return a.length-b.length;
				for(int i=0;i<a.length;++i) if(a[i]!=b[i]) return a[i]-b[i];
				return 0;
			}
		});
		int N=0;
		int[] a;
		int[][] c;
		Scanner sc = new Scanner(System.in);
		String ss = sc.nextLine();
		StringTokenizer st = new StringTokenizer(ss);
		while(st.hasMoreTokens()) {
			++N;
			st.nextToken();
		}
		st = new StringTokenizer(ss);
		a = new int[N];
		c = new int[N][N];
		for(int i=0;i<N;++i) a[i] = Integer.parseInt(st.nextToken());
		for(int i=0;i<N;++i) for(int j=0;j<N;++j) c[i][j] = sc.nextInt();
		
		Queue<int[]> q = new LinkedList<int[]>();
		
		q.add(a);
		ma.put( a, 0);
		int result = 1000000000;
		
		while(!q.isEmpty()) {
			int[] u = q.remove();
			int step = ma.get(u);
			boolean ok = true;
			for(int i=0;i<u.length-1;++i) if(u[i]>u[i+1]) ok = false;
			if(ok) result = Math.min( result, step);
			for(int i=0;i<u.length;++i) for(int j=i+1;j<u.length;++j) {
				int[] v = u.clone();
				int tt = v[i]; v[i] = v[j]; v[j] = tt;
				if(ma.containsKey(v)) {
					int oldStep = ma.get(v);
					if(oldStep>step+c[i][j]) {
						Integer I = step + c[i][j];
						ma.put(v, I);
						q.add(v);
					}
				}
				else {
					ma.put(v, step + c[i][j]);
					q.add(v);
				}
			}
		}
		
		System.out.println(result);
	}
}

Download