CHESSCBG - Bàn cờ thế

Tác giả: khuc_tuan

Ngôn ngữ: Java

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		char[][] a = new char[8][];
		for (int i = 0; i < a.length; ++i)
			a[i] = sc.nextLine().toCharArray();
		int[][] pos = new int[16][];
		int np = 0;
		for (int i = 0; i < a.length; ++i)
			for (int j = 0; j < a[i].length; ++j)
				if (a[i][j] == '1')
					pos[np++] = new int[] { i >= 4 ? i - 4 : i, j };
		int[][] cost = new int[8][8];
		for (int i = 0; i < 8; ++i)
			for (int j = 0; j < 8; ++j)
				cost[i][j] = Math.abs(pos[i][0] - pos[j + 8][0])
						+ Math.abs(pos[i][1] - pos[j + 8][1]);

		int[] F = new int[1 << 8];

		F[0] = 0;
		for (int i = 1; i < (1 << 8); ++i) {
			F[i] = Integer.MAX_VALUE;
			int c = -1;
			for (int j = 0; j < 8; ++j)
				if ((i & (1 << j)) != 0)
					++c;

			for (int j = 0; j < 8; ++j)
				if ((i & (1 << j)) != 0)
					F[i] = Math.min(F[i], F[i ^ (1 << j)] + cost[c][j]);
		}

		System.out.println(F[(1 << 8) - 1]);
	}
}

Download