/*
* Problem :: 2234 / 성곽
*
* Kind :: BFS
*
* Insight
* - 벽을 어떻게 다루면 좋을까...?
* + 3차원으로 생각하자!
* # 서쪽=0, 북쪽=1, 동쪽=2, 남쪽=3 이라고 하면,
* (i,j) 좌표의 북쪽에 벽이 있을 경우
* (bool) isWall[i][j][1] = true 로 다룰 수 있다
*
* - 벽을 다루는 것 외에는 전형적인 DFS, BFS 문제
* + 다만, 3의 답(하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기) 의 경우,
* 이를 계산하기 위해서 DFS, BFS 를 매 칸마다 다시 도는 것은 비효율적이다
* # 한번 DFS 또는 BFS 돌때 각 칸을 라벨링(labeling) 해주자
* -> 같은 방이면 같은 라벨을 가지게끔 하고
* 그 라벨에 해당하는 방의 개수를 저장해두면
* 인접한 칸을 조사해보는 것만으로도 3의 답을 알 수 있다!
* (같은 라벨이면 같은 방, 다른 라벨이면 다른 방)
*
* Point
* - 벽의 유무를 확인할 때
* 문제의 설명대로 비트연산을 활용하자
*
* - 방의 넓이를 구하는 데는 DFS 보다 BFS 가 나을 것 같아서
* BFS 를 사용하였다
*/
//
// BOJ
// ver.C++
//
// Created by GGlifer
//
// Open Source
#include <iostream>
#include <map>
#include <queue>
using namespace std;
#define endl '\n'
// Set up : Global Variables
int M, N;
bool isWall[50][50][4];
bool isVisited[50][50];
int label[50][50];
map<int,int> S;
int dy[4] = {0, -1, 0, +1}; /* 서쪽=0, 북쪽=1, 동쪽=2, 남쪽=3 */
int dx[4] = {-1, 0, +1, 0};
struct Point { int y, x; };
// Set up : Functions Declaration
bool isValid(int y, int x);
int bfs(int sy, int sx, int no);
int main()
{
// Set up : I/O
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Set up : Input
cin >> N >> M;
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++) {
int val; cin >> val;
for (int k=0; k<4; k++) {
if (val & (1<<k)) { /* 비트 연산을 활용하여 벽의 유무 판별 */
isWall[i][j][k] = true;
}
}
}
}
// Process
int ans1 = 0, ans2 = -1; /* ans1 = 방의 개수, ans2 = 가장 넓은 방의 넓이 */
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++) {
if (not(isVisited[i][j])) { /* 방문하지 않은 칸을 만나면 */
ans1++; /* 방의 개수 증가 */
int size = bfs(i, j, ans1); /* BFS 로 방의 넓이 구함 */
S[ans1]= size; /* 방의 개수를 라벨로 하여 방의 넓이를 저장 */
ans2 = max(ans2, size); /* 가장 넓은 방의 넓이 갱신 */
}
}
}
int ans3 = -1; /* ans3 = 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기 */
for (int i=0; i<M; i++) {
for (int j=0; j<N; j++) { /* (i,j) 에서 */
for (int k=0; k<4; k++) { /* 차례로 서쪽, 북쪽, 동쪽, 남쪽에 벽이 있다면 */
if (isWall[i][j][k]) {
int ay = i + dy[k]; /* 그 방향으로 인접한 칸의 좌표를 구함 */
int ax = j + dx[k];
if (isValid(ay, ax)) { /* 유효하면 */
int l1 = label[i][j]; /* 현재 칸의 라벨 */
int l2 = label[ay][ax]; /* 인접한 칸의 라벨 */
if (l1 != l2) { /* 같은 방이 아니면 */
ans3 = max(ans3, S[l1]+S[l2]);
}
}
}
}
}
}
// Control : Output
cout << ans1 << endl;
cout << ans2 << endl;
cout << ans3 << endl;
}
// Helper Functions
bool isValid(int y, int x)
/* 좌표 (y,x) 가 유효하면 true 를 반환, 그 외 false 를 반환 */
{
return y >= 0 && y < M && x >= 0 && x < N;
}
int bfs(int sy, int sx, int no)
/* 좌표 (sy,sx) 가 포함된 방의 넓이를 반환
* 그 방에 포함된 좌표들은 no 로 라벨링 됨 */
{
queue<Point> que;
que.push({sy, sx});
isVisited[sy][sx] = true;
int size = 0; /* 방의 넓이 */
while (not(que.empty())) {
int cy = que.front().y;
int cx = que.front().x;
que.pop();
size++; /* 방의 넓이 증가 */
label[cy][cx] = no; /* 라벨링 */
for (int i=0; i<4; i++) {
int ny = cy + dy[i];
int nx = cx + dx[i];
/* 좌표 (ny,nx) 가 유효하고 방문된 적이 없으며 사이에 벽이 없다면 */
if (isValid(ny, nx) && not(isVisited[ny][nx]) && not(isWall[cy][cx][i])) {
/* 방문 처리 */
isVisited[ny][nx] = true;
que.push({ny, nx});
}
}
}
return size;
}