15686 Samsung sw test

์ฝ”๋“œ

#include <iostream>
#define MAX_WIDTH 50
#define MAX_CHIKEN 13
 
using namespace std;
 
typedef struct Location {
	int row;
	int col;
} Location;
 
int width, maxChiken, numOfHouse, numOfChiken;
Location house[2 * MAX_WIDTH];
Location chiken[MAX_CHIKEN];
int minDistance = 10000000;
int index[MAX_CHIKEN];
 
void findMinChikenDistance(int deep = 0, int len = 0);
 
int main() {
	cin >> width >> maxChiken;
	for (int i = 0; i < width; i++) {
		for (int j = 0; j < width; j++) {
			int temp;
			cin >> temp;
			if (temp == 1)
				house[numOfHouse++] = { i, j };
			else if (temp == 2)
				chiken[numOfChiken++] = { i, j };
		}
	}
 
 
	findMinChikenDistance();
	cout << minDistance;
}
 
void findMinChikenDistance(int deep, int len) {
	if (len == maxChiken) {
		//๊ฒ€์‚ฌ
		int distance = 0;
		for (int h = 0; h < numOfHouse; h++) {
			int min = 100000000;
			for (int c = 0; c < maxChiken; c++) {
				int rowD = house[h].row - chiken[index[c]].row;
				int colD = house[h].col - chiken[index[c]].col;
				rowD = rowD < 0 ? (-1) * rowD : rowD;
				colD = colD < 0 ? (-1) * colD : colD;
				min = (rowD + colD) < min ? (rowD + colD) : min;
			}
			distance += min;
		}
		minDistance = distance < minDistance ? distance : minDistance;
		return;
	}
	if (numOfChiken - deep < maxChiken - len)
		return;
 
	index[len] = deep;
	findMinChikenDistance(deep + 1, len + 1);
	findMinChikenDistance(deep + 1, len);
}