algorithms software expert

소프트웨어 익스퍼트 2117 (software expert 2117)

소프트웨어 익스퍼트 2117 (software expert 2117)

목차

소프트웨어 익스퍼트 2117

코드

import java.io.*;
import java.util.StringTokenizer;

public class SWE2117 {
    static int t, T, n, m, v, map[][] = new int[20][20];
    static String ins[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        t = T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (T-- != 0) {
            ins = br.readLine().split(" ");
            n = Integer.parseInt(ins[0]);
            m = Integer.parseInt(ins[1]);
            StringTokenizer st;
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                v = 0;
                while (st.hasMoreTokens()) {
                    map[i][v++] = Integer.parseInt(st.nextToken());
                }
            }
            int ans = 0;
            for (int i = 1; i < n + 5; i++) {
                ans = Math.max(ans, getMaxService(getMask(i - 1), i - 1));
            }
            sb.append("#");sb.append(t - T);sb.append(" ");
            sb.append(ans);sb.append("\n");
        }
        bw.write(sb.toString());
        bw.flush();bw.close();
    }

    private static int getMaxService(int[][] mask, int k) {
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, getMaxCustommer(i, j, mask, k));
            }
        }
        return ans;
    }

    private static int getMaxCustommer(int x, int y, int[][] mask, int k) {
        int cost = 0, install = (k * k + (k + 1) * (k + 1)), count = 0;
        for (int i = x - k; i <= x + k; i++) {
            for (int j = y - k; j <= y + k; j++) {
                if (i < 0 || j < 0 || i > n - 1 || j > n - 1) continue;
                cost += ((map[i][j] & mask[i - (x - k)][j - (y - k)]) == 1) ? m : 0;
                count += ((map[i][j] & mask[i - (x - k)][j - (y - k)]) == 1) ? 1 : 0;
            }
        }
        return (cost - install < 0) ? -1 : count;
    }

    private static int[][] getMask(int k) {
        int mask[][] = new int[(k << 1) + 1][(k << 1) + 1];
        for (int i = 0; i < mask.length; i++) {
            for (int j = 0; j < mask.length; j++) {
                if (Math.abs(k - i) + Math.abs(k - j) <= k)
                    mask[i][j] = 1;
            }
        }
        return mask;   
    }


}

설명

Copied to clipboard