[SWEA] 2117. 홈 방범 서비스

풀이

#include <iostream>
#include <string.h>
#include <math.h>
#include <vector>

#define MAX 21

using namespace std;

int T, N, M;
int house[MAX][MAX];
int K, rst;
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };

void init() {
    cin >> N >> M;
    memset(house, 0, sizeof(house));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> house[i][j];
        }
    }
    rst = 0;
}

void calculate(int x, int y) {
    int cost = K * K + (K - 1) * (K - 1);
    int reward = 0;
    int house_count = 0;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (abs(x - i) + abs(y - j) <= K - 1) {
                if (house[i][j]) {
                    house_count++;
                    reward += M;
                }
            }
        }
    }
    if (cost <= reward) {
        if (rst < house_count) rst = house_count;
    }
}

void solve() {
    int max_K = N + 1;
    for (K = 1; K <= max_K; K++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                calculate(i, j);
            }
        }
    }
}

int main() {
    cin >> T;
    vector <int> v;
    for (int tc = 0; tc < T; tc++) {
        init();
        solve();
        v.push_back(rst);
    }
    for (int tc = 0; tc < T; tc++) {
        cout << "#" << tc + 1 << " " << v[tc] << endl;
    }
}