[SWEA 1949] 등산로 조정

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

#include <iostream>

#include <algorithm>

using namespace std;

 

#define MAX_N 9

 

int N, K, result, max_num;

int map[MAX_N][MAX_N];

bool check[MAX_N][MAX_N], used;

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

 

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

{

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

    {

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

 

        if (nexti >= 0 && nexti <= N - 1 && nextj >= 0 && nextj <= N - 1 && !check[nexti][nextj])

        {

            if (map[i][j] > map[nexti][nextj])

            {

                check[nexti][nextj] = true;

                dfs(nexti, nextj, count + 1);

                check[nexti][nextj] = false;

            }

            else if (!used && map[i][j] > map[nexti][nextj] - K && !check[nexti][nextj])

            {

                int tmp = map[nexti][nextj];

                used = true; map[nexti][nextj] = map[i][j]-1; check[nexti][nextj] = true;

                dfs(nexti, nextj, count + 1);

                used = false; map[nexti][nextj] = tmp; check[nexti][nextj] = false;

            }

        }

 

        result = max(result, count);

    }

}

 

void cal()

{

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

    {

        for (int j = 0; j < N; j++)

        {

            if (map[i][j] == max_num)

            {

                check[i][j] = true;

                dfs(i, j, 1);

                check[i][j] = false;

            }

        }

    }

}

 

int main()

{

    int T; int tc = 1;

    cin >> T;

    while (T--)

    {

        cin >> N >> K; max_num = 0; result = 0; used = false;

        for (int i = 0; i < N; i++) for (int j = 0; j < N; j++)

        {

            check[i][j] = false;

            cin >> map[i][j];

            max_num = max(max_num, map[i][j]);

        }

        cal();

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

        tc++;

    }

 

    return 0;

}