문제:
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누
www.acmicpc.net
코드:
visited 재방문 허용 필요
visited 재방문 위해서 dfs에서 return 전 visited 초기화 필요, 도중 return하더라도 초기화 가능토록(goto)
하드코딩 더블 체크
#include <iostream>
#define f(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
int R, C;
int map[500][500];
int ans;
// dfs
bool vst[500][500];
int dr[] = { -1, 0, 1, 0 };
int dc[] = { 0, 1, 0, -1 };
void dfs(int r, int c, int s, int l) {
vst[r][c] = 1;
s += map[r][c];
if (l == 4){
if(s > ans)
ans = s;
goto out;
}
f(d, 4) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || R <= nr || nc < 0 || C <= nc) continue;
if (vst[nr][nc]) continue;
dfs(nr, nc, s, l + 1);
}
out:
vst[r][c] = 0;
}
// ㅗ
int hw[4][2] = { {2, 3}, {3, 2}, {2, 3}, {3, 2} };
int blk[4][4][2] = {
{{0, 1}, {1, 0}, {1, 1}, {1, 2}},
{{0, 0}, {1, 0}, {1, 1}, {2, 0}},
{{0, 0}, {0, 1}, {0, 2}, {1, 1}},
{{0, 1}, {1, 0}, {1, 1}, {2, 1}}
};
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> R >> C;
f(r, R) f(c, C) cin >> map[r][c];
f(r, R) f(c, C) dfs(r, c, 0, 1);
f(d, 4) f(r, R - hw[d][0] + 1) f(c, C - hw[d][1] + 1) {
int s = 0;
f(b, 4)
s += map[r + blk[d][b][0]][c + blk[d][b][1]];
if (s > ans)
ans = s;
}
cout << ans;
return 0;
}