#pragma warning(disable:4996) #include<iostream> #include<algorithm> #define MAX 502 using namespace std; int map[MAX][MAX]; bool visit[MAX][MAX]; int n, m, tmp; int dx[4] = { 0,0,1,-1 }; int dy[4] = { 1,-1,0,0 }; int dfs(int x, int y, int d) { if (d == 4) return map[x][y]; visit[x][y] = 1; int ret = 0; 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; if (visit[nx][ny]) continue; tmp = dfs(nx, ny, d + 1); ret = max(ret, tmp); } visit[x][y] = 0; return ret + map[x][y]; } int other(int x, int y) { int sum = map[x][y], min_value = 2000; for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; sum += map[nx][ny]; min_value = min(min_value, map[nx][ny]); } return sum - min_value; } int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) scanf("%d", &map[i][j]); int ret_max = 0; for(int i=0; i<n;i++) for (int j = 0; j < m; j++) { int value = max(dfs(i, j, 1), other(i, j)); ret_max = max(value, ret_max); } printf("%d\n", ret_max); } |
dfs 를 사용해서 완전탐색을 합니다. 여기서 dfs 의 변수는 x, y, d 입니다. d==4 는 하나의 모형을 의미합니다. 그리고 회전, 대칭 모두 가능하기 때문에! 그리고 테트로미노의 전형적인 패턴 이므로 이것을 틀로 생각합니다. return map[x][y] 입니다. 그리고 visit[x][y] =1로 변경해주고, 이것은 다른 dfs 와 달리 map 을 변경하지는 않습니다. 다른 마지막 끝단 즉 4번쨰 블럭의 크기를 비교합니다. 그리고 그것을 return 하면서 계속 하나씩 쌓아갑니다. 오케이
그리고 other 함수의 경우에는 십자가 모양의 블록을 의미합니다. return 값은 십자모양중 가장 작은 값을 뺀값입니다. 그렇게 해야 다른 모형과의 최대값을 비교할 수 있습니다.