문제링크 : https://www.acmicpc.net/problem/14500
문제설명
.
DFS, 백트래킹을 이용하면 쉽게 풀 수있는 문제다.
블럭의 종류는 탐색 시 깊이가 4인 블럭들과 아닌 보라색 블럭으로 나눠져있습니다 여기서 말하는 깊이가 4인 블럭들의 의미는 , 예를들어 (1,1) 좌표로 부터 시작해서 (?,?) 좌표까지 깊이가 4인 블럭들을 말합니다.
하지만, 보라색블럭은 깊이가 4가 되는것이 불가능하기 때문에 따로 확인을 해줘야한다. 또한 블록이 회전한 경우도 고려해줘야합니다!
코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | #include <iostream> #include <algorithm> using namespace std; int dx[4] = {0,0,1,-1}; int dy[4] = {1,-1,0,0}; int shape_x1[4][4] = {{0,0,1,0},{0,1,1,2},{0,0,-1,0},{0,1,1,2}}; // ㅏ ㅗ ㅓ ㅜ 모양 int shape_y1[4][4] = {{0,1,1,2},{0,0,1,0},{0,1,1,2},{0,0,-1,0}}; int a, b, maxx, mmax; int map[501][501]; bool bmap[501][501]; void shapecheck(int x, int y) // dfs ㅗ ㅏ ㅜ ㅓ 체크 { for (int j = 0; j < 4; j++) { mmax = 0; for (int i = 0; i < 4; i++) { int xx = x + shape_x1[j][i]; int yy = y + shape_y1[j][i]; if (xx >= 1 && yy >= 1 && xx <= b && yy <= a) { mmax += map[yy][xx]; } else { break; } } maxx = max(mmax,maxx); } } void dfs(int result, int sum, int x, int y) // 4 모양 체크 { if (result == 4) { maxx = max(maxx,sum); return ; } for (int i = 0; i < 4; i++) { int xx = x + dx[i]; int yy = y + dy[i]; if (xx >= 1 && yy >= 1 && xx <= b && yy <= a && !bmap[yy][xx]) { bmap[yy][xx] = true; dfs(result+1, sum + map[yy][xx], xx,yy); bmap[yy][xx] = false; } } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> a >> b; for (int i = 1; i <= a; i++) { for (int j = 1; j <= b; j++) { cin >> map[i][j]; } } for (int i = 1; i <= a; i++) { for (int j = 1; j <= b; j++) { bmap[i][j] = true; dfs(1,map[i][j],j,i); bmap[i][j] = false; shapecheck(j,i); } } cout << maxx; return 0; } | cs |
