[SWEA 2383] 점심 식사시간

SWEA::2383::점심 식사시간

출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5-BEE6AK0DFAVl

#include <bits/stdc++.h>

using namespace std;

struct P { int y, x; };

int T, t = 1, N, a[10][10], c[10], s[2], ans, pn, ps=0;

vector<P> vp,vs[2]; vector<int> q[2];

int cal(int r) {

q[0].clear(); q[1].clear();

for (int i = 0; i < pn; i++) q[c[i]].push_back(vs[c[i]][i].y);

sort(q[0].begin(), q[0].end()); sort(q[1].begin(), q[1].end());

for (int j = 0; j < 2; j++) {

if (q[j].size()) {

for (int i = 0; i < q[j].size(); i++) {

if (i > 2) {

if (q[j][i - 3] > q[j][i]) q[j][i] = (q[j][i - 3] + s[j]);

else q[j][i] = (q[j][i] + s[j] + 1);

continue;

}

q[j][i] += (s[j] + 1);

}

r = max(r, q[j][q[j].size()-1]);

}

}

return r;

}

int main() {

ios::sync_with_stdio(0); cin.tie(0); cin >> T;

while (T--) {

cin >> N; vp.clear(); vs[0].clear(); vs[1].clear(); ans = 1e9; ps = 0; memset(c, 0, sizeof(c));

for (int i = 0; i < N; i++)for (int j = 0; j < N; j++) {

cin >> a[i][j];

if (a[i][j] == 1) vp.push_back({ i,j });

else if (a[i][j]>0) { vs[ps].push_back({ i,j }); s[ps++] = a[i][j]; }

}pn = vp.size();

for (int i = 0; i < 2; i++) for (int j = 0; j < pn; j++) vs[i].push_back({ (abs(vp[j].y-vs[i][0].y) + abs(vp[j].x-vs[i][0].x)),0 });

vs[0].erase(vs[0].begin()); vs[1].erase(vs[1].begin());

for (int i = 0; i < pow(2, pn); i++) {

for (int j = 0; j < pn; j++) {

if (i&(1 << j)) c[j] = 0;

else c[j] = 1;

}

ans = min(ans,cal(0));

}

cout << "#" << t++ << " " << ans << '\n';

}

return 0;

}