[백준] 14500번. 테트로미노 (C++)

문제

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

풀이

[DFS+노가다]

 

4번 이동하는 모든 경우의 수를 생각해보자

위와 같은 경우 등등이 있을 것이다.

 

어라 그런데 뭔가 보인다!

짜잔! 도형들을 회전하거나 대칭 시킨 모양과 동일하다!

그렇기 때문에 dfs를 사용해서 해결하면된다

 

 

그런데 ㅗ 모양은 저 경우에 대입할 수 없다

그렇기 때문에 이 경우는 노가다로 진행한다

 

코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int dir[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };
int answer = 0;
int map[502][502];
int visited[502][502];
int n, m;

void dfs(int x, int y, int count, int sum)
{
    if (count == 4) {
        answer = (sum > answer) ? sum : answer;
        return;
    }
    for (int i = 0; i < 4; i++)
    {
        int nextX = x + dir[i][0];
        int nextY = y + dir[i][1];
        if (nextX < 0 || nextY < 0 || nextX >= m || nextY >= n)continue;
        if (visited[nextY][nextX] != 0)continue;

        visited[nextY][nextX] = 1;
        dfs(nextX, nextY, count + 1, sum + map[nextY][nextX]);
        visited[nextY][nextX] = 0;
    }
}
int main()
{
    //INPUT
    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < m; k++)
        {
            cin >> map[i][k];
        }
    }

    //DFS
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < m; k++)
        {
            visited[i][k] = 1;
            dfs(k, i, 1, map[i][k]);
            visited[i][k] = 0;
        }
    }



    //ㅗ CASE 
    for (int i = 0; i < n; i++)
    {
        for (int k = 0; k < m; k++)
        {
            int case1 = 0, case2 = 0, case3 = 0, case4 = 0;

            // case ㅜ
            if (i + 1 < n && k - 1 >= 0 && k + 1 < m) {
                case1 = map[i][k] + map[i][k - 1] + map[i][k + 1] + map[i + 1][k];
            }

            // case ㅗ
            if (i - 1 >= 0 && k - 1 >= 0 && k + 1 < m) {
                case2 = map[i][k] + map[i][k - 1] + map[i][k + 1] + map[i - 1][k];
            }

            // case ㅓ
            if (i - 1 >= 0 && i + 1 < n && k - 1 >= 0) {
                case3 = map[i][k] + map[i - 1][k] + map[i + 1][k] + map[i][k - 1];
            }

            // case ㅏ
            if (i - 1 >= 0 && i + 1 < n && k + 1 < m) {
                case4 = map[i][k] + map[i - 1][k] + map[i + 1][k] + map[i][k + 1];
            }

            int m = max(max(case1, case2), max(case3, case4));
            answer = max(answer, m);
        }
    }

    //RESULT
    cout << answer;
    return 0;
}