[Java]BOJ 14500テルミノ(ブルートフォス)

BOJ 14500 G 5三軌制

gold5

実施

🔍 問題の説明

https://www.acmicpc.net/problem/14500
ポリオミの黄色の大きさは1×複数の1人の正方形でつながっている図形で、以下の条件を満たす必要があります.

正方形は互いに重ならない.

図形はすべてつながっています.

正方形のエッジの間には接続されているはずです.つまり、必ずしも頂点と重なる必要はありません.

4つの正方形を結ぶポリオミノをトロミノといい、以下の5種類があります.

美しい大きさはN×Mの紙にトロミノを置きます.紙は1×1つの大きさのセルに分けられ、各セルに整数が書かれています.
1つのトロミノを適当な位置に置いて、プログラムを書いて、トロミノを置いた格子に書いた数字の和を最大化します.
トロミノは正方形を置いて正確にセルを含み、回転したり対称にしたりする必要があります.

✔入力

第1行目は、用紙の長手方向サイズNおよび横方向サイズMを与える.(4 ≤ N, M ≤ 500)
2行目からN行の紙に数字が書いてあります.i 1行目のj個の数字は、上からiの1番目のセル、左からjの1番目のセルに書かれた数字である.入力は1000を超えない自然数を与えます.

✔出力

最初の行では、トロミノが格子に置かれた数字の和の最値を出力します.

💡 に答える

トロミノは2種類に分かれています.

(i,j)から4コマ移動可閲覧タイプ

.

(i,j)から4格子を再帰関数とし,アクセス不可タイプ(ㅒ,ㅒ,ㅒ)

そして、1番タイプは4コマ移動し、最大のmax sumを見つけました.

	private static void dfs(int x, int y, int cnt, int sum) {
		if(cnt==4) {
			max = Math.max(sum, max);
			return;
		}
		
		for(int d=0; d<4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if(!isIn(nx,ny)) continue;
			if(visited[nx][ny]) continue;
			
			visited[nx][ny] = true;
			dfs(nx,ny,cnt+1,sum+map[nx][ny]);
			visited[nx][ny] = false;
		}
	}

第2類はif文でㅎ,ㅎ,ㅎ,ㅄを区別し,状況数の和についてmax検査を行った.

	private static void find(int i, int j) {
		//ㅏ
		if(i-1>=0&&i+1<N&&j+1<M) {
			int sum = map[i][j] + map[i-1][j] + map[i+1][j] + map[i][j+1];
			max = Math.max(sum, max);
		}
		//ㅓ
		if(i-1>=0&&i+1<N&&j-1>=0) {
			int sum = map[i][j] + map[i-1][j] + map[i+1][j] + map[i][j-1];
			max = Math.max(sum, max);
		}
		//ㅗ
		if(i-1>=0&&j-1>=0&j+1<M) {
			int sum = map[i][j] + map[i-1][j] + map[i][j-1] + map[i][j+1];
			max = Math.max(sum, max);
		}
		//ㅜ
		if(i+1<N&&j-1>=0&j+1<M) {
			int sum = map[i][j] + map[i+1][j] + map[i][j-1] + map[i][j+1];
			max = Math.max(sum, max);
		}
	}

💬 ソースコード

package week30;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main_BOJ_14500_G5_테트로미노 {
	static int N, M, map[][], max;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static boolean[][] visited;
	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];
		visited = new boolean[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());
			}
		}
	
		
		for(int i = 0 ; i < N; i++) {
			for (int j = 0; j < M; j++) {
				visited[i][j] = true;
				dfs(i,j,1,map[i][j]);
				find(i,j);
				visited[i][j] = false;
			}
		}
		
		System.out.println(max);
	}

	private static void dfs(int x, int y, int cnt, int sum) {
		if(cnt==4) {
			max = Math.max(sum, max);
			return;
		}
		
		for(int d=0; d<4; d++) {
			int nx = x + dx[d];
			int ny = y + dy[d];
			
			if(!isIn(nx,ny)) continue;
			if(visited[nx][ny]) continue;
			
			visited[nx][ny] = true;
			dfs(nx,ny,cnt+1,sum+map[nx][ny]);
			visited[nx][ny] = false;
		}
	}

	private static void find(int i, int j) {
		//ㅏ
		if(i-1>=0&&i+1<N&&j+1<M) {
			int sum = map[i][j] + map[i-1][j] + map[i+1][j] + map[i][j+1];
			max = Math.max(sum, max);
		}
		//ㅓ
		if(i-1>=0&&i+1<N&&j-1>=0) {
			int sum = map[i][j] + map[i-1][j] + map[i+1][j] + map[i][j-1];
			max = Math.max(sum, max);
		}
		//ㅗ
		if(i-1>=0&&j-1>=0&j+1<M) {
			int sum = map[i][j] + map[i-1][j] + map[i][j-1] + map[i][j+1];
			max = Math.max(sum, max);
		}
		//ㅜ
		if(i+1<N&&j-1>=0&j+1<M) {
			int sum = map[i][j] + map[i+1][j] + map[i][j-1] + map[i][j+1];
			max = Math.max(sum, max);
		}
	}

	
	private static boolean isIn(int nx, int ny) {
		if(nx<0||ny<0||nx>=N||ny>=M) return false;
		return true;
	}

}

💯 採点結果

33348 KBメモリ
時間704ミリ秒