[백준 14500]테트로미노

문제  https://www.acmicpc.net/problem/14500

1)문제분류

-DFS

-부루트포스

2)문제해결

- 아이디어 문제인 듯하다.  모양을 일일히 만들어서 하드코딩으로 구현하는 방법도 있지만, 

재귀로 카운트 4까지만 센다면, 테트리스 모양이 나오게 된다.  단, ㅗ 모양 빼고!!

그래서 ㅗ 모양은 하드코딩으로 ㅏ ㅓ ㅜ ㅗ 최댓값을 구한다.

#include<iostream>

#include<algorithm>

using namespace std;

int n, m;

int map[502][502];

bool chk[502][502];

int ans = 0;

int xrr[4] = { 0,0,1,-1 };

int yrr[4] = { 1,-1,0,0 };

bool range(int rx, int ry)

{

if (rx<0 || ry<0 || rx>n - 1 || ry>m - 1)return false;

else return true;

}

void dfs(int x, int y, int cnt, int hap)

{

if (cnt >= 4)return;

for (int i = 0; i < 4; i++)

{

int cx = x + xrr[i];

int cy = y + yrr[i];

if (range(cx, cy) == false||chk[cx][cy]==true)continue;

if (chk[cx][cy] == false)

{

chk[cx][cy] = true;

ans = max(hap + map[cx][cy], ans);

dfs(cx, cy, cnt + 1, hap + map[cx][cy]); 

chk[cx][cy] = false;

}

}

}

void ex(int x, int y)

{

if (range(x - 1, y) && range(x, y - 1) && range(x, y + 1))

ans = max(ans, map[x - 1][y] + map[x][y] + map[x][y - 1] + map[x][y + 1]);

if (range(x +1, y) && range(x, y - 1) && range(x, y + 1))

ans = max(ans, map[x+1][y] + map[x][y] + map[x][y - 1] + map[x][y + 1]);

if (range(x + 1, y) && range(x-1, y) && range(x, y-1))

ans = max(ans, map[x + 1][y] + map[x][y] + map[x-1][y] + map[x][y-1]);

if (range(x + 1, y) && range(x-1, y) && range(x, y + 1))

ans = max(ans, map[x + 1][y] + map[x][y] + map[x-1][y] + map[x][y + 1]);

}

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++)

{

chk[i][j] = true;

dfs(i, j, 1,map[i][j]);

ex(i, j);

chk[i][j] = false;

}

}

cout << ans << endl;

}