boj 15686: 치킨배달

import java.util.*;

public class Main {
	public static final int[] dr = { -1, 0, 0, 1 };
	public static final int[] dc = { 0, -1, 1, 0 };

	public static final int SPACE = 0;
	public static final int HOME = 1;
	public static final int CHICKEN = 2;

	public static int min = Integer.MAX_VALUE;

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int size = in.nextInt();
		int chickenNum = in.nextInt();

		int mat[][] = new int[size][size];
		ArrayList<Point> chickens = new ArrayList<Point>();
		ArrayList<Point> homes = new ArrayList<Point>();

		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				int position = in.nextInt();

				if (position == CHICKEN) {
					chickens.add(new Point(i, j));
				} else if (position == HOME) {
					homes.add(new Point(i, j));
				}
			}
		}

		for (int i = 0; i < chickens.size(); i++) {
			boolean check[] = new boolean[chickens.size()];
			check[i] = true;
			findAll(mat, homes, chickens, i, 1, chickenNum, check);
		}

		System.out.println(min);
	}

	public static void findAll(int mat[][], ArrayList<Point> homes, ArrayList<Point> chickens, int index, int num,
			int chickenNum, boolean[] check) {
		if (num == chickenNum) {
			min = Math.min(min, calcChickenDistance(mat, homes, chickens, check));
			return;
		}
		if (index == chickens.size()) {
			return;
		}

		for (int i = index + 1; i < chickens.size(); i++) {
			check[i] = true;
			findAll(mat, homes, chickens, i, num + 1, chickenNum, check);
			check[i] = false;
		}
	}

	public static int calcChickenDistance(int mat[][], ArrayList<Point> homes, ArrayList<Point> chickens,
			boolean[] check) {
		int distanceSum = 0;
		for (Point home : homes) {
			int distance = Integer.MAX_VALUE;
			for (int i = 0; i < check.length; i++) {
				if (check[i]) {
					Point chicken = chickens.get(i);
					distance = Math.min(distance, Math.abs(home.row - chicken.row) + Math.abs(home.col - chicken.col));
				}
			}
			distanceSum += distance;
		}

		return distanceSum;
	}
}

class Point {
	int row;
	int col;

	public Point(int row, int col) {
		this.row = row;
		this.col = col;
	}
}