SWEA-2117 홈 방범 서비스

마름모 모양을 구현하기 위해 num이라는 수를 사용했다. 

현재 위치한 행-num부터~ 현재 위치한 행+num까지로 행의 마름모 모양을 구현했다.

열의 마름모 모양은 i열보다 작으면 k를 늘려서 점점 검사하는 열이 많아지게 했고, 그렇지 않다면 k를 줄여서 점점 검사하는 열을 줄였다. 

운영비용은 문제의 식과 같은 방식으로 구현을 했다.

0~n-1(도시의 크기-1)까지의 모든 마름모를 구현한 뒤에 최댓값을 반환하는 함수로 구현했다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

using namespace std;

int n, m, maximum;
int map[20][20];

int cal(int num) {
    if (num > n) {
        return maximum;
    }

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
        {
            int k = 0;
            int home = 0;
            for (int nowx = i - num; nowx <= i + num; nowx++) {
                for (int nowy = j - k; nowy <= j + k; nowy++)
                {
                    if (map[nowx][nowy] == 1 && nowy >= 0 && nowx >= 0 && nowy < n && nowx < n)
                        home++;
                }
                if (nowx < i) 
                    k++;
                else
                    k--;
            }

            if (home * m - (num * num + (num + 1) * (num + 1)) >= 0)
                if (home > maximum)
                    maximum = home;
        }

    cal(num + 1);
}

int main()
{
	int T;
    cin>>T;
    for (int tc = 1; tc <= T; tc++)
    {
       memset(map, 0, sizeof(map));

        cin>>n>>m;
        for(int i=0; i<n; i++){
        	for(int j=0; j<n; j++){
        		cin>>map[i][j];
			}
		}
        maximum=0;
        //cal(0);
        cout<<"#"<<tc<<" "<<cal(0)<<"\n";
    }
}