algorithms software expert

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

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

목차

소프트웨어 익스퍼트 4014

코드

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

public class SWE4014 {
    static int t, T, n, x, map[][] = new int[20][20], v;
    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]);
            x = 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 = 0; i < n; i++) {
                ans += getNumOfInstall(i, 0, map);
                ans += getNumOfInstall(i, 1, map);
            }

            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 getNumOfInstall(int m, int r, int[][] mp) {
        boolean isPath = true, load[] = new boolean[n];
        int map[][] = new int[20][20];
        if (r == 0) map = mp;
        else {
            for (int i = 0; i < 20; i++) {
                for (int j = 0; j < 20; j++) {
                    map[j][i] = mp[i][j];
                }
            }
        }
        if (map[m][0] < map[m][1] || map[m][n - 2] > map[m][n - 1]) return 0;
        for (int i = 0; i < n - 1; i++) {
            int cur = map[m][i], next = map[m][i + 1];
            if (cur == next) continue;
            if (Math.abs(cur - next) > 1) return 0;
            if (cur - next == 1) {
                if (isFlat(next, i + 2, i + x  + 1, m, map, load)) {
                    for (int j = 1; j < x + 1; j++) load[i + j] = true;
                } else isPath = false;
            }else {
                if (isFlat(map[m][i - 1], i - x + 1, i, m, map, load)) {
                    for (int j = i - x + 1; j <= i; j++) load[j] = true;
                } else isPath = false;
            }
            if (!isPath) return 0;
        }
        return 1;
    }


    private static boolean isFlat(int standard, int s, int e, int m, int[][] map, boolean[] l) {
        if (s < 0 || e > n) return false;
        for (int i = s; i < e; i++) {
            if (l[i]) return false;
            if (standard != map[m][i]) return false;
        }
        return true;
    }
}

설명

Copied to clipboard