[백준] 14500 테트로미노

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main_bj_14500 {
	static int[] di = { 0, 1, 0, -1 };
	static int[] dj = { 1, 0, -1, 0 };
	static int N, M;
	static int[][] num;
	static boolean[][] visited;
	static int[][] open;
	static Queue<Point> queue;

	static boolean check(int i, int j) {
		if (i >= 0 && i < N && j >= 0 && j < M)
			return true;
		else
			return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		N = sc.nextInt();
		M = sc.nextInt();

		num = new int[N][M];
		open = new int[N][M];
		visited = new boolean[N][M];

		int max = 0;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				num[i][j] = sc.nextInt();
				max = num[i][j] > max ? num[i][j] : max;
			}
		}
		
		queue = new LinkedList<>();
		int cnt = 4;
		while (cnt > 0) {
			boolean flag = true;
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < M; j++) {
					open[i][j] = num[i][j];
					queue.add(new Point(i, j));

					if (open[i][j] == 0 && flag)
						flag = false;
				}
			}

			if (flag)
				break;

			while (!queue.isEmpty()) {
				int size = queue.size();

				for (int s = 0; s < size; s++) {
					Point now = queue.poll();
					visited[now.i][now.j] = true;
					for (int d = 0; d < 4; d++) {
						int ni = now.i + di[d];
						int nj = now.j + dj[d];

						if (check(ni, nj) && !visited[ni][nj] && num[ni][nj] >= max) {
							queue.add(new Point(ni, nj));
							open[ni][nj] = num[ni][nj];
						}
					}
				}
				cnt--;
			} // end queue while
			max--;
		}

		for (int i = 0; i < N; i++) {
			Arrays.fill(visited[i], false);
		}
		queue.clear();

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (open[i][j] != 0 && !visited[i][j]) {
					visited[i][j] = true;
					dfs(i, j, 1, open[i][j]);
					for (int k = 0; k < N; k++) {
						Arrays.fill(visited[k], false);
					}
				}
			}
		}

		System.out.println(max_result);
	}

	static int max_result = 0;

	static void dfs(int i, int j, int cnt, int sum) {
		visited[i][j] = true;
		if (cnt == 4) {
			max_result = sum > max_result ? sum : max_result;
			return;
		}

		if (cnt == 2) {
			int tmp = sum;
			if (check(i - 1, j) && !visited[i - 1][j] && check(i + 1, j) && !visited[i + 1][j]) {
				tmp += open[i - 1][j];
				tmp += open[i + 1][j];
				max_result = tmp > max_result ? tmp : max_result;
			}

			tmp = sum;
			if (check(i, j - 1) && !visited[i][j - 1] && check(i, j + 1) && !visited[i][j + 1]) {
				tmp += open[i][j - 1];
				tmp += open[i][j + 1];
				max_result = tmp > max_result ? tmp : max_result;
			}
		}

		for (int d = 0; d < 4; d++) {
			int ni = i + di[d];
			int nj = j + dj[d];

			if (check(ni, nj) && !visited[ni][nj] && open[ni][nj] != 0) {
				visited[ni][nj] = true;
				dfs(ni, nj, cnt + 1, sum + open[ni][nj]);
				visited[ni][nj] = false;
			}
		}
	}

	static void print() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				System.out.print(open[i][j] + " ");
			}
			System.out.println();
		}
	}

	static class Point {
		int i, j;

		public Point(int i, int j) {
			this.i = i;
			this.j = j;
		}

		@Override
		public String toString() {
			return "Point [i=" + i + ", j=" + j + "]";
		}
	}
}