15812번: 침략자 진아
2차원 공간의 세로의 크기와 가로의 크기를 의미하는 두 정수 N, M(2 ≤ N, M ≤ 20)이 주어진다. 예제 입력과 같이 마을의 지도가 주어진다. 0은 빈 공간을, 1은 마을이 있는 공간을 의미한다.
www.acmicpc.net
#include <stdio.h>
#include <algorithm>
using namespace std;
int N, M;
char map[20][21];
int house[398][2], space[399][2];
int housen, spacen;
int ans = 400;
int main() {
scanf("%d%d", &N, &M);
for (int r = 0; r < N; ++r) {
scanf("%s", map[r]);
for (int c = 0; c < M; ++c) {
if (map[r][c] == '1') {
house[housen][0] = r;
house[housen][1] = c;
++housen;
}
else {
space[spacen][0] = r;
space[spacen][1] = c;
++spacen;
}
}
}
for (int s1 = 0; s1 < spacen; ++s1) {
for (int s2 = s1 + 1; s2 < spacen; ++s2) {
int max_cst = 0;
for (int h = 0; h < housen; ++h) {
max_cst = max(max_cst, min(abs(space[s1][0] - house[h][0]) + abs(space[s1][1] - house[h][1]), abs(space[s2][0] - house[h][0]) + abs(space[s2][1] - house[h][1])));
if (max_cst > ans) {
goto out;
}
}
ans = min(ans, max_cst);
out:
continue;
}
}
printf("%d", ans);
return 0;
}
