알고리즘 문제풀이/백준
[백준 14500] 테트로미노
홍시홍
2020. 2. 2. 16:28
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
요구사항
주어진 맵에서 이어진 4칸의 최대합 구하기
풀이
1. dfs로 4칸 정하기
2. 4칸의 합이 최대인지 검사
3. ㅏ모양은 dfs로 검사 안됨. ㅏ 모양이 되는 조건 확인
4. 정답 출력
#include <iostream>
#include <algorithm>
using namespace std;
int map[501][501];
int visit[501][501];
int n, m;
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,-1,0,1 };
int ans = 0;
void dfs(int r, int c, int cnt,int sum) {
if (cnt == 4) {
ans = max(ans, sum);
return;
}
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr < 0 || nc < 0 || nr >= n || nc >= m) {
continue;
}
if (visit[nr][nc] == 0) {
visit[nr][nc] = 1;
dfs(nr, nc, cnt + 1, sum + map[nr][nc]);
visit[nr][nc] = 0;
}
}
}
void sum1(int r, int c) {
int temp = map[r][c] + map[r + 1][c] + map[r - 1][c] + map[r][c + 1];
ans = max(ans, temp);
}
void sum2(int r, int c) {
int temp = map[r][c] + map[r -1][c] + map[r][c-1] + map[r][c + 1];
ans = max(ans, temp);
}
void sum3(int r, int c) {
int temp = map[r][c] + map[r + 1][c] + map[r - 1][c] + map[r][c - 1];
ans = max(ans, temp);
}
void sum4(int r, int c) {
int temp = map[r][c] + map[r + 1][c] + map[r][c-1] + map[r][c + 1];
ans = max(ans, temp);
}
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++) {
visit[i][j] = 1;
dfs(i, j, 1,map[i][j]);
visit[i][j] = 0;
if (i > 0 && i < n - 1 && j >= 0 && j < m - 1)
sum1(i, j);
if (i > 0 && i <= n - 1 && j > 0 && j < m - 1)
sum2(i, j);
if (i > 0 && i < n - 1 && j > 0 && j <= m - 1)
sum3(i, j);
if (i >= 0 && i < n - 1 && j > 0 && j < m - 1)
sum4(i, j);
}
}
cout << ans << endl;
}