[SWEA 2105] 디저트 카페

출처 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do

#include <iostream>

#include <algorithm>

using namespace std;

 

#define MAX_N 20

 

int N, result, starti, startj;

int map[MAX_N][MAX_N];

bool used[101];

int dir[4][2] = { { 1,1 },{ 1,-1 },{ -1,-1 },{ -1,1 } };

 

void dfs(int i, int j, int count, int comdrc)

{

    used[map[i][j]] = true;

 

    if (i-1 == starti && j+1 == startj)

    {

        result = max(result, count);

        used[map[i][j]] = false;

        return;

    }

 

    for (int c = comdrc; c < comdrc+2; c++)

    {

        if (c == 4) break;

        int nexti = i + dir[c][0]; int nextj = j + dir[c][1];

        if (nexti < N && nexti >= 0 && nextj < N && nextj >= 0 && !used[map[nexti][nextj]])

        {

            dfs(nexti, nextj, count + 1, c);

        }

    }

 

    used[map[i][j]] = false;

}

 

void cal()

{

    for (int i = 0; i < N-2; i++)

    {

        for (int j = 1; j < N-1; j++)

        {

            if (map[i][j] != map[i + 1][j + 1] && map[i][j] != map[i+1][j-1])

            {

                starti = i; startj = j; used[map[i][j]] = true;

                dfs(i+1, j+1, 2, 0);

                used[map[i][j]] = false;

            }

        }

    }

}

 

int main()

{

    int T; int tc = 1;

    cin >> T;

    while (T--)

    {

        cin >> N; result = 0;

        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)   cin >> map[i][j];

        for (int i = 0; i < 101; i++) used[i] = false;

 

        cal();

 

        if (result == 0) result = -1;

        cout << "#" << tc++ << " " << result << endl;

    }

 

    return 0;

}