백준 14502번 C++

#include <iostream>

#include <cstring>

#include <vector>

using namespace std;

const int MAX = 8;

int lab[MAX][MAX];

int labcopy[MAX][MAX];

int m, n;

vector<pair<int, int>> emptyroom;

typedef struct {

int x, y;

}Move;

Move mv[4] = { {-1,0},{1,0},{0,1},{0,-1} };

void dfs(int i, int j) {

for (int k = 0; k < 4; k++) {

int ma = i + mv[k].x;

int mb = j + mv[k].y;

if (ma >= 0 && ma < n && mb >= 0 && mb < m) {

if (labcopy[ma][mb] == 0) {

labcopy[ma][mb] = 2;

dfs(ma, mb);

}

}

}

}

int main(void) {

cin >> n >> m;

int safearea = 0;

for (int i = 0; i < n; i++) {

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

cin >> lab[i][j];

if (lab[i][j] == 0)

emptyroom.push_back(make_pair(i, j));

}

}

for (int i = 0; i < emptyroom.size()-2; i++) {

for (int j = i + 1; j < emptyroom.size() - 1; j++) {

for (int k = j + 1; k < emptyroom.size(); k++) {

pair<int, int> first = emptyroom[i];

pair<int, int> second = emptyroom[j];

pair<int, int> third = emptyroom[k];

for (int a = 0; a < n; a++) {

for (int b = 0; b < m; b++) {

labcopy[a][b] = lab[a][b];

}

}

labcopy[first.first][first.second] = 1;

labcopy[second.first][second.second] = 1;

labcopy[third.first][third.second] = 1;

for (int x = 0; x < n; x++) {

for (int y = 0; y < m; y++) {

if (labcopy[x][y] == 2)

dfs(x, y);

}

}

int zero = 0;

for (int a = 0; a < n; a++) {

for (int b = 0; b < m; b++) {

if (labcopy[a][b] == 0)

zero++;

}

}

if (zero > safearea)

safearea = zero;

}

}

}

cout << safearea;

}