728x90
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
위 5개 도형 중 차례대로 4개는 DFS를 사용해서 간단히 구할 수 있다. 하지만 마지막 'ㅗ' 도형은 DFS로 만들 수 없으므로 예외도형으로 빼주어야 한다. 따라서, 모든 점에서 DFS 도는 함수, 예외 도형 찾는 함수 두개만 작성하면 된다.
예외도형은 i와 j를 이용해서 중심에서 3방향을 돌면서 찾아준다.
마지막 도형을 예외로 생각해주는게 난관이었다. 그것만 처리해주면 DFS 구현하는 것은 쉽다.
#include <iostream>
#include <algorithm>
using namespace std;
int N, M, board[505][505], result;
int dx[] = { -1,0,0,1 }, dy[] = { 0,-1,1,0 };
bool check[505][505];
void tetromino(int x , int y, int four, int cnt) {
if (four >= 3) {
result = max(result, cnt);
return;
}
for (int i = 0; i < 4; i++) {
int xx = x + dx[i], yy = y + dy[i];
if (xx >= 0 && xx < N && yy >= 0 && yy < M && !check[xx][yy]) {
check[xx][yy] = true;
tetromino(xx, yy, four + 1, cnt + board[xx][yy]);
check[xx][yy] = false;
}
}
}
void tetromino_special(int x, int y) {
for (int i = 0; i < 4; i++) {
int cnt = board[x][y];
bool flag = true; //블럭이 만들어졌는가
for (int j = 0; j < 3; j++) {
int xx = x + dx[(i + j) % 4];
int yy = y + dy[(i + j) % 4];
if (xx >= 0 && xx < N && yy >= 0 && yy < M) {
cnt += board[xx][yy];
}
else {
flag = false; //블럭이 만들어지지 않음
break;
}
}
if(flag) result = max(result, cnt);
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> board[i][j];
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
check[i][j] = true;
tetromino(i, j, 0, board[i][j]);
tetromino_special(i, j);
check[i][j] = false;
//cout << "( "<<i<<", " << j <<" ) : " << result << "\n";
}
}
cout << result << "\n";
return 0;
}728x90
