SWEA 문제모음

 

12712 파리퇴치

• dfs로 하나하나 계산하는 것보다 누적합으로 구하는 게 빠를 것 같아 그렇게 해줬다
• 좌 -> 우 누적합 배열, 상 -> 하 누적합 배열, 좌상 -> 우하 누적합, 우상 -> 좌하 누적합 배열을 만들어줌
• 그리고 각각 지점에서 잡을 수 있는 파리 수를 계산해준다

 

public class Solution {
    static int n;
    static int m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        for (int tc=1; tc<=tcCnt; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken())-1;

            int[][] horizonSum = new int[n+1][n+1];
            int[][] verticalSum = new int[n+1][n+1];
            int[][] diagonalRightSum = new int[n+1][n+1];
            int[][] diagonalLeftSum = new int[n+1][n+1];

            for (int i =1; i<=n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j =1; j<=n; j++) {
                    int value = Integer.parseInt(st.nextToken());

                    horizonSum[i][j] = horizonSum[i][j-1] + value;
                    verticalSum[i][j] = verticalSum[i-1][j] + value;

                    diagonalRightSum[i][j] = diagonalRightSum[i-1][j-1] + value;
                    diagonalLeftSum[i][j] = value;
                    if (j < n) {
                        diagonalLeftSum[i][j] += diagonalLeftSum[i-1][j+1];
                    }
                }
            }

            int max = 0;
            for (int i =1; i<=n; i++) {
                for (int j =1; j<=n; j++) {
                    int currentValue = verticalSum[i][j] - verticalSum[i-1][j];
                    int value = getVerticalHorizontalSum(verticalSum, horizonSum, i, j, currentValue);

                    if (value > max)
                        max = value;

                    value = getDiagonalSum(diagonalRightSum, diagonalLeftSum, i, j, currentValue);

                    if (value > max)
                        max = value;
                }
            }

            System.out.println("#" + tc + " " + max);
        }
    }

    public static int getVerticalHorizontalSum(int[][] verticalSum, int[][] horizonSum, int i, int j, int currentValue) {
        int sum =0;

        int right = (j+m >= n)? n: j+m;
        int left = (j-m-1 < 0)? 0: j-m-1;
        int down = (i+m >= n)? n: i+m;
        int up = (i-m-1 < 0)? 0: i-m-1;

        sum += horizonSum[i][right] - horizonSum[i][left];
        sum += verticalSum[down][j] - verticalSum[up][j];

        return sum - currentValue; //중복제거
    }

    public static int getDiagonalSum(int[][] diagonalRightSum, int[][] diagonalLeftSum, int i, int j, int currentValue) {
        int sum = 0;

        int diffDown = Math.min(m, n-i); //우하
        diffDown = Math.min(diffDown, n-j);
        int diffUp = Math.min(m+1, i); //좌상
        diffUp = Math.min(diffUp, j);

        sum += diagonalRightSum[i+diffDown][j+diffDown] - diagonalRightSum[i-diffUp][j-diffUp];

        diffDown = Math.min(m, n-i); //좌하
        diffDown = Math.min(diffDown, j-1);
        diffUp = Math.min(m+1, i); //우상
        diffUp = Math.min(diffUp, n-j);

        sum += diagonalLeftSum[i+diffDown][j-diffDown] - diagonalLeftSum[i-diffUp][j+diffUp];

        return sum - currentValue; //중복제거
    }
}

 

구현 쪽이 아직 많이 부족한 게 느껴진다. 더 좋은 풀이가 있을 거라고 생각한다.

 

 

 

 

1974 스도쿠 검증

• 각 칸마다 Set 하나씩, 각 열마다 Set 하나씩, 각 행마다 Set 하나씩 만들어서 다 넣어준다
• 크기 전부 9가 아니면 0출력, 전부 9면 1출력
• 각 칸은 3으로 나눈 몫을 기준으로 3x3 2차원 배열로 만들어줬다

 

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc=1; tc<=tcCnt; tc++) {
            HashSet<Integer>[][] area = new HashSet[3][3];
            for (int i =0; i<area.length; i++) {
                for (int j=0; j< area.length; j++) {
                    area[i][j] = new HashSet<>();
                }
            }
            // 012 345 678 3의 몫으로 구분, 012

            HashSet<Integer>[] row = new HashSet[9];
            for (int i =0; i<row.length; i++) {
                row[i] = new HashSet<>();
            }

            HashSet<Integer>[] col = new HashSet[9];
            for (int i =0; i<col.length; i++) {
                col[i] = new HashSet<>();
            }

            for (int i=0; i<9; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j =0; j<9; j++) {
                    int value = Integer.parseInt(st.nextToken());
                    col[i].add(value);
                    row[j].add(value);
                    area[i/3][j/3].add(value);
                }
            }

            boolean isGood = true;

            for (int i =0; i<9; i++) {
                if (row[i].size() != 9 || col[i].size() != 9) {
                    isGood = false;
                    break;
                }
            }

            for (int i =0; i<area.length; i++) {
                if (!isGood)
                    break;

                for (int j=0; j<area.length; j++) {
                    if (area[i][j].size() != 9) {
                        isGood = false;
                        break;
                    }
                }
            }

            sb.append("#" + tc + " ");
            if (isGood) {
                sb.append(1);
            } else {
                sb.append(0);
            }
            sb.append("\n");
        }

        System.out.println(sb);
    }
}

 

 

 

 

1961 숫자 배열 회전

• 잘 보면 규칙이 보인다
• 그냥 그대로 출력해주면 됨. 어렵지 않다

 

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc=1; tc<=tcCnt; tc++) {
            int n = Integer.parseInt(br.readLine());

            int[][] arr = new int[n][n];
            for (int i =0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j =0; j<n; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            sb.append("#" + tc + "\n");

            for (int i =0; i<n; i++) {
                for (int j =n-1; j>=0; j--) {
                    sb.append(arr[j][i]);
                }
                sb.append(" ");

                for (int j =n-1; j>=0; j--) {
                    sb.append(arr[n-1-i][j]);
                }
                sb.append(" ");

                for (int j =0; j<n; j++) {
                    sb.append(arr[j][n-1-i]);
                }
                sb.append("\n");
            }
        }

        System.out.println(sb);
    }
}

 

 

 

 

1959 두 개의 숫자열

• 브루트포스를 사용해야할 듯하다
• 범위는 0 ~ (maxSize - minSize) 로 돌리기

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= tcCnt; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = Integer.parseInt(st.nextToken());
            }

            st = new StringTokenizer(br.readLine());
            int[] arr2 = new int[m];
            for (int i = 0; i < m; i++) {
                arr2[i] = Integer.parseInt(st.nextToken());
            }

            int[] max;
            int[] min;
            if (n > m) {
                max = arr;
                min = arr2;
            } else {
                min = arr;
                max = arr2;
            }

            int maxValue = 0;
            for (int i = 0; i <= max.length - min.length; i++) {
                int tmp = 0;
                for (int j = 0; j < min.length; j++) {
                    tmp += min[j] * max[i + j];
                }

                if (tmp > maxValue) {
                    maxValue = tmp;
                }
            }

            sb.append("#" + tc + " " + maxValue + "\n");
        }

        System.out.print(sb);
    }
}

• 그냥 돌리면 된다

 

 

 

 

1204 1일차 - 최빈수 구하기

• 그냥 Map에 횟수를 저장하며 최빈수 구하면 될 듯

 

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= tcCnt; tc++) {
            Map<Integer, Integer> map = new HashMap<>();

            br.readLine();
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i =0; i<1000; i++) {
                int score = Integer.parseInt(st.nextToken());
                map.put(score, map.getOrDefault(score, 0) + 1);
            }

            int maxCnt = 0;
            int value = 0;
            for (int score: map.keySet()) {
                Integer cnt = map.get(score);
                if (cnt > maxCnt) {
                    value = score;
                    maxCnt = cnt;
                } else if (cnt == maxCnt) {
                    if (value < score) {
                        value = score;
                    }
                }
            }

            sb.append("#" + tc + " " + value + "\n");
        }

        System.out.print(sb);
    }
}

 

 

 

 

7465 창용 마을 무리의 개수

• 그래프탐색으로 찾아내면 되겠다
• visit 배열 쓰면 될듯
• bfs든 dfs든 상관 x

 

public class Solution {
    static ArrayList<Integer>[] arr;
    static boolean[] visit;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());


        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= tcCnt; tc++) {
            int result = 0;

            StringTokenizer st=  new StringTokenizer(br.readLine());
            int manCnt = Integer.parseInt(st.nextToken());
            int lineCnt = Integer.parseInt(st.nextToken());

            visit = new boolean[manCnt];
            arr = new ArrayList[manCnt];
            for (int i =0; i<arr.length; i++) {
                arr[i] = new ArrayList<>();
            }

            for (int i =0; i<lineCnt; i++) {
                st = new StringTokenizer(br.readLine());
                int a= Integer.parseInt(st.nextToken())-1;
                int b= Integer.parseInt(st.nextToken())-1;
                arr[a].add(b);
                arr[b].add(a);
            }

            for (int i =0; i<arr.length; i++) {
                if (!visit[i]) {
                    visit[i] = true;
                    dfs(i);
                    result ++;
                }
            }

            sb.append("#" + tc + " " + result + "\n");
        }

        System.out.print(sb);
    }

    private static void dfs(int num) {
        for (int adj: arr[num]) {
            if (!visit[adj]) {
                visit[adj] = true;
                dfs(adj);
            }
        }
    }
}

 

 

 

4193 수영대회 결승전 ( 완전 탐색 + 구현 )

• 풀이법이 제목에 써져있어서 재미없다. 난이도 상이라면서 왜 풀이법을 알려주지..
• 소용돌이 때문에 제자리에서 기다려야하는 경우도 있으므로, 완전탐색을 해야할 것 같다

 

class Location implements Comparable<Location> {
    int row;
    int col;
    int time;

    public Location(int row, int col, int time) {
        this.row = row;
        this.col = col;
        this.time = time;
    }

    @Override
    public int compareTo(Location o) {
        return time - o.time;
    }
}

public class Solution {
    static int result = 0;
    static int[][] times;
    static int[][] arr;

    static int[] rowStep = new int[]{0,0,-1,1};
    static int[] colStep = new int[]{-1,1,0,0};


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= tcCnt; tc++) {
            int n = Integer.parseInt(br.readLine());
            result = -1;

            arr = new int[n][n];
            times = new int[n][n];
            for (int i =0; i<times.length; i++) {
                Arrays.fill(times[i], 100000);
            }

            for (int i =0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                for (int j =0; j<n; j++) {
                    arr[i][j] = Integer.parseInt(st.nextToken());
                }
            }

            StringTokenizer st = new StringTokenizer(br.readLine());
            int startRow = Integer.parseInt(st.nextToken());
            int startCol = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            int endRow = Integer.parseInt(st.nextToken());
            int endCol = Integer.parseInt(st.nextToken());

            simulation(startRow, startCol, endRow, endCol);

            sb.append("#" + tc + " " + result + "\n");
        }

        System.out.print(sb);
    }

    private static void simulation(int startRow, int startCol, int endRow, int endCol) {
        PriorityQueue<Location> queue = new PriorityQueue<>();
        queue.add(new Location(startRow, startCol, 0));
        times[startRow][startCol] = -1;

        while (!queue.isEmpty()) {
            Location current = queue.poll();
            int row = current.row;
            int col = current.col;
            if (row == endRow && col == endCol) {
                result = current.time;
                break;
            }

            //움직이기
            for (int i =0; i<4; i++) {
                int tmpRow = row + rowStep[i];
                int tmpCol = col + colStep[i];

                if (canGo(tmpRow, tmpCol, current.time)) {
                    if (arr[tmpRow][tmpCol] == 2 && current.time % 3 != 2) {
                        //소용돌이인 상태
                        int time = current.time + (2 - current.time % 3);
                        if (time < times[tmpRow][tmpCol]) {
                            queue.add(new Location(tmpRow, tmpCol, time+1));
                            times[tmpRow][tmpCol] = time+1;
                        }
                    } else {
                        if (current.time+1 < times[tmpRow][tmpCol]) {
                            queue.add(new Location(tmpRow, tmpCol, current.time+1));
                            times[tmpRow][tmpCol] = current.time + 1;
                        }
                    }
                }
            }
        }
    }

    private static boolean canGo(int row, int col, int time) {
        if (row >= arr.length || row < 0 || col >= arr.length || col < 0) {
            return false;
        }

        if (arr[row][col] == 1) {
            return false;
        }

        if (times[row][col] <= time) {
            return false;
        }

        return true;
    }
}

• 문제를 제대로 읽어야한다
• 소용돌이 위에서 기다릴 수 있다는 걸 유의

 

 

1868 파핑파핑 지뢰찾기

• dfs bfs 냄새가 남
• 0을 먼저 눌러야 최소 횟수가 될 수 있다
• 0인 칸 먼저 눌러주면서 visit처리 해주고, 0인 칸 영역 주변 애들도 visit 처리 해주기
• 이후 0과 인접하지 않은(visit처리되지 않은) 개수 카운트

 

public class Main {
    static int[] rowStep = new int[]{-1,-1,-1,0,0,1,1,1};
    static int[] colStep = new int[]{-1,0,1,-1,1,-1,0,1};
    static boolean[][] visit;
    static char[][] arr;
    static int[][] numArr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc=1; tc<=tcCnt; tc++) {
            int n = Integer.parseInt(br.readLine());
            arr = new char[n][n];
            numArr = new int[n][n];
            visit = new boolean[n][n];

            for (int i =0; i<n; i++) {
                String input = br.readLine();
                for (int j=0; j<n; j++) {
                    arr[i][j] = input.charAt(j);
                }
            }

            for (int i =0; i<n; i++) {
                for (int j=0; j<n; j++) {
                    if (arr[i][j] == '*') {
                        numArr[i][j] = -1;
                        visit[i][j] = true;
                        for (int step = 0; step<rowStep.length; step++) {
                            int tmpRow = i+rowStep[step];
                            int tmpCol = j+colStep[step];
                            if (canAdd(tmpRow, tmpCol)) {
                                numArr[tmpRow][tmpCol] ++;
                            }
                        }
                    }
                }
            }

            int result = 0;
            for (int i =0; i<n; i++) {
                for (int j=0; j<n; j++) {
                    if (!visit[i][j] && numArr[i][j] == 0) {
                        dfs(i, j);
                        result++;
                    }
                }
            }

            for (int i =0; i<n; i++) {
                for (int j=0; j<n; j++) {
                    if (!visit[i][j]) {
                        result++;
                    }
                }
            }

            sb.append("#" + tc + " " + result + "\n");
        }
        System.out.print(sb);
    }

    private static void dfs(int row, int col) {
        visit[row][col] = true;

        for (int step = 0; step<rowStep.length; step++) {
            int tmpRow = row+rowStep[step];
            int tmpCol = col+colStep[step];
            if (isValidLocation(tmpRow, tmpCol)) {
                if (!visit[tmpRow][tmpCol] && numArr[tmpRow][tmpCol] == 0) {
                    dfs(tmpRow, tmpCol);
                } else {
                    visit[tmpRow][tmpCol] = true; //경계선 처리
                }
            }
        }
    }

    private static boolean canAdd(int row, int col) {
        if (isValidLocation(row, col)) {
            if (arr[row][col] != '*') {
                return true;
            }
        }

        return false;
    }

    private static boolean isValidLocation(int row, int col) {
        return row >= 0 && row < arr.length && col >= 0 && col < arr.length;
    }
}

 

 

 

 

1249 [S/W 문제해결 응용] 4일차 - 보급로

• PriorityQueue에 복구시간을 넣으면서 bfs해주면 되겠다
• 다익스트라네

 

class Location implements Comparable<Location> {
    int row;
    int col;
    int time;

    public Location(int row, int col, int time) {
        this.row = row;
        this.col = col;
        this.time = time;
    }

    @Override
    public int compareTo(Location o) {
        return time - o.time;
    }
}

public class Main {
    static int[][] map;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc=1; tc<=tcCnt; tc++) {
            int size = Integer.parseInt(br.readLine());

            map = new int[size][size];

            for (int i=0; i<size; i++) {
                String input = br.readLine();
                for (int j=0; j<size; j++) {
                    map[i][j] = Character.getNumericValue(input.charAt(j));
                }
            }

            int result = dijkstra(0, 0, size - 1, size - 1);

            sb.append("#" + tc + " " + result + "\n");
        }
        System.out.print(sb);
    }

    static int[] rowStep = new int[]{-1,1,0,0};
    static int[] colStep = new int[]{0,0,-1,1};

    private static int dijkstra(int startRow, int startCol, int endRow, int endCol) {
        PriorityQueue<Location> pq = new PriorityQueue<>();
        pq.add(new Location(startRow, startCol, 0));

        int[][] values = new int[map.length][map.length];
        for (int i=0; i<values.length; i++) {
            Arrays.fill(values[i], Integer.MAX_VALUE);
        }
        values[startRow][startCol] = 0;

        while (!pq.isEmpty()) {
            Location current = pq.poll();

            if (current.row == endRow && current.col == endCol) {
                break;
            }

            for (int step =0; step<4; step++) {
                int nextRow = current.row + rowStep[step];
                int nextCol = current.col + colStep[step];

                if (canGo(nextRow, nextCol) && values[nextRow][nextCol] > values[current.row][current.col] + map[nextRow][nextCol]) {
                    values[nextRow][nextCol] = values[current.row][current.col] + map[nextRow][nextCol];
                    pq.add(new Location(nextRow, nextCol, values[nextRow][nextCol]));
                }
            }
        }

        return values[endRow][endCol];
    }

    private static boolean canGo(int row, int col) {
        if (row >= 0 && row < map.length && col >= 0 && col < map.length) {
            return true;
        }

        return false;
    }
}

• 최근에 다익스트라 뿌수기를 해서 어렵지 않게 풀었다

 

 

 

 

1248 [S/W 문제해결 응용] 3일차 - 공통조상

• 최근에 트리를 부수면서 공통조상 알고리즘을 접했음
• 공통조상을 알아낸 후, 해당 노드부터 자식을 순회하며 서브트리 크기를 찾아내면 될 것 같다
• parent와 depth를 저장하는 배열이 필요, 간선들 관계도 ArrayList배열에 저장하자

 

public class Main {
    static ArrayList<Integer>[] arr;
    static int[] parent;
    static int[] depth;
    static int a;
    static int b;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc=1; tc<=tcCnt; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int nodeCnt = Integer.parseInt(st.nextToken());
            int lineCnt = Integer.parseInt(st.nextToken());
            a = Integer.parseInt(st.nextToken())-1;
            b = Integer.parseInt(st.nextToken())-1;

            parent = new int[nodeCnt];
            depth = new int[nodeCnt];
            arr=  new ArrayList[nodeCnt];
            for (int i =0; i<arr.length; i++) {
                arr[i] = new ArrayList<>();
            }

            st = new StringTokenizer(br.readLine());
            for (int i =0; i<lineCnt; i++) {
                int p = Integer.parseInt(st.nextToken())-1;
                int child = Integer.parseInt(st.nextToken())-1;

                arr[p].add(child);
                parent[child] = p;
            }

            dfs(0, 0);

            while (depth[a] > depth[b]) {
                a = parent[a];
            }

            while (depth[a] < depth[b]) {
                b = parent[b];
            }

            while (a != b) {
                a = parent[a];
                b = parent[b];
            }

            int cnt = countChildren(a);

            sb.append("#" + tc + " " + (a+1) + " " + cnt + "\n");
        }

        System.out.print(sb);
    }

    private static int countChildren(int node) {
        int cnt = 1;
        for (int child: arr[node]) {
            cnt += countChildren(child);
        }

        return cnt;
    }

    private static void dfs(int node, int d) {
        depth[node] = d;

        for (int child: arr[node]) {
            dfs(child, d+1);
        }
    }
}

• 메모리를 많이 써서 메모리 초과가 날 줄 알았는데 안났다
• 은근 pass 기준이 널널한 것 같음 

 

 

 

 

1247 3일차 - 최적 경로

• 방문후 돌아오는 경로.. 짧은 거 찾기문제다
• 문제에 다익스트라를 쓰지말라는 식으로 명시되어있다
• 고객의 수가 적은 걸 보면 모든 경우를 탐색해도 될 것 같다 10*9*8*7*6*5*...
• N * N 배열로 서로 간 거리를 저장한 후, dfs치면서 백트래킹을 수행하면 될듯

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Location {
    int x;
    int y;

    public Location(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int clientCnt;
    static Location[] locs;
    static int[][] arr;
    static int minDistance = Integer.MAX_VALUE;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tcCnt = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        for (int tc=1; tc<=tcCnt; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            clientCnt = Integer.parseInt(st.nextToken());
            arr = new int[clientCnt+2][clientCnt+2];
            locs = new Location[clientCnt+2];

            st = new StringTokenizer(br.readLine());
            for (int i =0; i<arr.length; i++) {
                locs[i] = new Location(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
            }

            for (int i =0; i<arr.length; i++) {
                for (int j =0; j<arr.length; j++) {
                    if (i == j) {
                        arr[i][j] = 0;
                        continue;
                    }
                    int distance = Math.abs(locs[i].x - locs[j].x) + Math.abs(locs[i].y - locs[j].y);

                    arr[i][j] = distance;
                    arr[j][i] = distance;
                }
            }

            visit = new boolean[clientCnt+2];
            minDistance = Integer.MAX_VALUE;
            dfs(0,1, 1, 0);

            sb.append("#" + tc + " " + minDistance + "\n");
        }

        System.out.print(sb);
    }

    private static void dfs(int current, int end, int cnt, int sum) {
        if (cnt == clientCnt+1) {
            sum += arr[current][end];
            if (minDistance > sum) {
                minDistance = sum;
                return;
            }
        }

        if (sum > minDistance) {
            return;
        }

        visit[current] = true;

        for (int i =2; i<locs.length; i++) {
            if (!visit[i]) {
                dfs(i, end, cnt+1, sum + arr[current][i]);
            }
        }

        visit[current] = false;
    }
}