15686번

15686

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
int map[50][50];
bool visit[50][50];
int dist[50][50];
int answer = 987654321;
vector<pair<int, int> > house;
vector<pair<int, int> > chickenHouse;

void initAll() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			visit[i][j] = false;
			dist[i][j] = 987654321;
		}
	}
}

void initDist() {
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			dist[i][j] = 987654321;
		}
	}
}

int getDist(int x1, int y1, int x2, int y2) {
	return abs(x2 - x1) + abs(y2 - y1);
}

void dfs(int cnt, int chickenIndex, vector<pair<int, int> > visitChickenHouse) {
	if (cnt == visitChickenHouse.size()) {
		initDist();

		for (int i = 0; i < visitChickenHouse.size(); i++) {
			int chicken_x = visitChickenHouse[i].first;
			int chicken_y = visitChickenHouse[i].second;

			for (int j = 0; j < house.size(); j++) {
				int house_x = house[j].first;
				int house_y = house[j].second;

				dist[house_x][house_y] = min(getDist(chicken_x, chicken_y, house_x, house_y), dist[house_x][house_y]);
			}
		}

		int sum = 0;
		for (int j = 0; j < house.size(); j++) {
			sum += dist[house[j].first][house[j].second];
		}
		answer = min(sum, answer);
		return;
	}

	for (int i = chickenIndex; i < chickenHouse.size(); i++) {
		int chicken_x = chickenHouse[i].first;
		int chicken_y = chickenHouse[i].second;
		if (!visit[chicken_x][chicken_y]) {
			visitChickenHouse.push_back(make_pair(chicken_x, chicken_y));
			visit[chicken_x][chicken_y] = true;

			dfs(cnt, i, visitChickenHouse);

			visitChickenHouse.pop_back();
			visit[chicken_x][chicken_y] = false;
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			if (map[i][j] == 1) { //집 
				house.push_back(make_pair(i, j));
			}
			else if (map[i][j] == 2) {
				chickenHouse.push_back(make_pair(i, j));
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		initAll();
		vector<pair<int, int> > visitChickenHouse;
		dfs(i, 0, visitChickenHouse);
	}
	cout << answer;
	return 0;
}