https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
ㅗㅓㅏㅜ모양을 제외한 블럭들은 상하좌우방향으로 탐색을 4번까지 하면 구해진다.
그러므로, ㅗㅓㅏㅜ모양과 일반적인 블럭들을 따로 처리해주었다.
[JAVA}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N,M,ans=0;
static int[][] map;
static boolean[][] visit;
static int[] dx= {0,0,1,-1};
static int[] dy= {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];
visit=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++) {
visit[i][j]=true;
dfs(i,j,1,map[i][j]);
visit[i][j]=false;
unusual(i,j);
}
}
System.out.println(ans);
}
private static void unusual(int x, int y) {
if((x==0&&y==0) ||(x==0&&y==M-1) || (x==N-1&&y==0) || (x==N-1 &&y==M-1))
return;
int cnt=1;
int total=map[x][y];
for(int i=0; i<4; i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0||ny<0||nx>=N||ny>=M) continue;
cnt++;
total+=map[nx][ny];
}
if(cnt==4) {
if(ans<total)ans=total;
}else if(cnt==5) {
for(int i=0; i<4; i++) {
int nx=x+dx[i];
int ny=y+dy[i];
int tmp=total-map[nx][ny];
if(ans<tmp) ans=tmp;
}
}
}
private static void dfs(int x, int y, int cnt, int sum) {
if(cnt==4) {
if(ans<sum)ans=sum;
return;
}
for(int i=0; i<4; i++) {
int nx=x+dx[i];
int ny=y+dy[i];
if(nx<0||ny<0||nx>=N||ny>=M||visit[nx][ny]==true)continue;
visit[nx][ny]=true;
dfs(nx,ny,cnt+1,sum+map[nx][ny]);
visit[nx][ny]=false;
}
}
}
[C++]
#include <iostream>
#include <algorithm>
using namespace std;
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int N,M;
int map[500][500];
int ans=0;
bool visited[500][500]={0,};
//일반적인 경우 (ㅗ모양 제외한 경우)
void DFS(int x, int y, int depth, int sum){
if(depth==4){
if(ans < sum) ans = sum;
return;
}
visited[x][y]=1;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || ny<0 || nx>=N || ny>=M || visited[nx][ny]) continue;
DFS(nx,ny,depth+1,sum+map[nx][ny]);
}
visited[x][y]=0;
}
//ㅗ의 경우 ( 4방향 모두 더한 값에서 제일작은칸의 값 빼서 ㅗ ㅏ ㅜ ㅓ 중 가장 큰 값구함
void SpCase(int x, int y, int sum){
int cnt=0;//범위 벗어난 횟수 카운트하기위한 변수
int minVal=10000;
for(int i=0; i<4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if(nx<0 || ny<0 || nx>=N || ny>=M){
cnt++; continue;//범위 벗어난 수 카운트하기
}
sum+=map[nx][ny];
minVal = min(minVal, map[nx][ny]);
}
if(cnt>1) return;//범위 2번이상 벗어나면 ㅗ모양이 안되서 리턴
if(cnt==1){//범위 1번만 벗어난 경우: ㅗ모양이기 떄문에 최솟값 뺄 필요없음
ans = max(ans,sum);
}
if(cnt==0){//4방향 모두더한 경우 :값이 제일 작은 칸빼기
ans = max(ans,sum-minVal);
}
}
int main(){
cin >> N >> M;
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
cin >> map[i][j];
}
}
//일반적인 경우
for(int i=0; i<N; i++){
for(int j=0; j<M; j++){
DFS(i, j, 1, map[i][j]);
}
}
//ㅗ모양 탐색
for(int i=0; i<N; i++)for(int j=0; j<M; j++){
SpCase(i,j, map[i][j]);
}
cout << ans;
return 0;
}
댓글