[SWEA 2117] 홈 방범 서비스

출처 :https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V61LqAf8DFAWu

#include <iostream>

#include <algorithm>

using namespace std;

 

int N, M, K, result, MAX_K, num;

int map[20][20];

 

void square(int i, int j, int depth)

{

    int starti = i; int startj = j;

    while (1)

    {

        if (i >= 0 && j >= 0 && i < N && j < N)

        {

            if (map[i][j]) num++;

        }

        i--;j++;

        if (i == starti - depth && j == startj + depth) break;

    }

    while (1)

    {

        if (i >= 0 && j >= 0 && i < N && j < N)

        {

            if (map[i][j]) num++;

        }

        i++;j++;

        if (i == starti && j == startj + 2*depth) break;

    }

    while (1)

    {

        if (i >= 0 && j >= 0 && i < N && j < N)

        {

            if (map[i][j]) num++;

        }

        i++;j--;

        if (i == starti + depth && j == startj + depth) break;

    }

    while (1)

    {

        if (i >= 0 && j >= 0 && i < N && j < N)

        {

            if (map[i][j]) num++;

        }

        i--;j--;

        if (i == starti && j == startj) break;

    }

 

}

 

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

{

    while (depth <= MAX_K)

    {

        int starti = i; int startj = j - depth;

        square(starti, startj, depth);

        depth++;

        if ((num*M) - ((depth*depth) + (depth - 1)*(depth - 1)) >= 0) result = max(result, num);

    }

}

 

 

int main()

{

    int T; int tc = 1;

    cin >> T;

    while (T--)

    {  

        cin >> N >> M; result = 0; K = 0;

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

        {

            cin >> map[i][j]; K += map[i][j];

        }

        for (int i = 50; i > 0; i--) if (((i * i) + ((i - 1) * (i - 1))) <= K*M) { MAX_K = i; break; }

         

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

        {

            if (map[i][j]) { num = 1; dfs(i, j, 1); }

            else { num = 0; dfs(i, j, 1); }

        }

        if (result == 0) result = 1;

 

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

    }

         

    return 0;

}