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]);
}
}