[BOJ] 14500 테트로미노

 

 

[문제]

https://www.acmicpc.net/problem/14500

 

 

[소스 코드]

import java.io.*;
import java.util.*;

public class Main {
	static int n,m,result;
	static int[][] map;
	static boolean[][] visit;
	static int[] dr = {0,0,-1,1};
	static int[] dc = {1,-1,0,0};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new int[n][m];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<m;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		result = 0;
		visit = new boolean[n][m];
		for(int i=0;i<n;i++) {
			for(int j=0;j<m;j++) {
				visit[i][j] = true;
				dfs(i,j,1,map[i][j]);
				visit[i][j] = false;
			}
		}
		System.out.println(result);
	}
	private static void dfs(int r,int c,int cnt,int sum) {
		if(cnt==4) {
			result = Math.max(result, sum);
			return;
		}
		for(int d=0;d<4;d++) {
			int nr = r + dr[d];
			int nc = c + dc[d];
			if(nr<0 || nr>=n || nc<0 || nc>=m) continue;
			if(!visit[nr][nc]) {
				visit[nr][nc] = true;
				dfs(nr,nc,cnt+1,sum+map[nr][nc]);
				if(cnt==2) dfs(r,c,cnt+1,sum+map[nr][nc]);
				visit[nr][nc] = false;
			}
		}
	}
}