문제 링크

https://www.codetree.ai/training-field/frequent-problems/problems/maze-runner/description?page=3&pageSize=20

풀이

배열 회전과 위치 갱신이 복잡한 문제였다.

구현 자체는 문제 조건에서 지정한 대로 따라가면 된다.

구현에서 신경을 썼던 부분은 아래와 같다.

1. 모든 사람이 탈출하고 나서 회전하는 경우
2. 배열을 회전하고 나서 사람의 위치를 갱신하는 경우

1번은 모두 탈출했는지 탐색하고 나서 이동과 회전을 진행했는데, 회전할 정사각형의 범위를 0으로 초기화 해줘야 했다.

2번은 인덱스 매칭으로 회전한 위치를 구해야 한다.

처음에는 맵을 회전할때에는

1. 사람과 출구 위치를 맵에 넣음
2. 회전 범위에 따라 회전
3. 회전하면서 사람 위치와 출구라면 새로운 위치로 갱신해줌

이런 로직이었는데 다음과 같은 예시에서 문제가 생겼다.

이때 위의 로직을 따르면 사람 1명을 먼저 갱신하고 사람 2명의 위치에서 모든 사람의 위치가 하나로 갱신되는 문제가 있었다.

따라서 다음과 같이 로직을 변경했다

1. 사람 수만큼 반복문
2. 현재 사람이 탈출하지 않았고, 회전 범위에 있는지 확인
3. 회전 범위에 있다면 (0,0) 기준으로 위치를 이동
4. [x][y] -> [y][박스크기 - x - 1] 공식 적용
5. 기준점으로 위치 이동한 만큼 다시 더해줌

이 부분을 조심해서 풀었다.

코드

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

public class Main {
    static class Pos {
        int x, y;
        boolean isOut;

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

        public Pos(int x, int y, boolean isOut) {
            this.x = x;
            this.y = y;
            this.isOut = isOut;
        }
    }

    static int N, M, K, map[][], copy[][], total;
    static Pos exit; //출구 위치
    static int bx, by, boxSize; //회전할 박스 시작행열, 사이즈 저장
    static Pos[] p; //사람들 좌표 저장

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        N = Integer.parseInt(tokens.nextToken()); //맵
        M = Integer.parseInt(tokens.nextToken()); //사람
        K = Integer.parseInt(tokens.nextToken()); //게임시간

        map = new int[N][N];
        p = new Pos[M];
        total = 0;

        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }

        for (int i = 0; i < M; i++) {
            tokens = new StringTokenizer(br.readLine());
            p[i] = new Pos(Integer.parseInt(tokens.nextToken()) - 1,
                    Integer.parseInt(tokens.nextToken()) - 1,
                    false);
        }

        tokens = new StringTokenizer(br.readLine());
        exit = new Pos(Integer.parseInt(tokens.nextToken()) - 1,
                Integer.parseInt(tokens.nextToken()) - 1);
        //end input

        while (K-- > 0) {
            //모든 참가자가 탈출했는지 확인
            if (isAllOut()) break;

            for (int i = 0; i < M; i++) {
                movePeople(i); //모든 참가자 이동
                //이동했는데 출구인지 확인
                if (p[i].x == exit.x && p[i].y == exit.y) {
                    p[i].isOut = true;
                }
            }

            bx = by = boxSize = 0; //모두 탈출하고 회전시킬 경우
            findRect(); //상자 사이즈 찾음

            rotateRect(); //미로 회전
        }

        exit.x++;
        exit.y++;
        System.out.println(total);
        System.out.println(exit.x + " " + exit.y);
    }

    private static boolean isAllOut() {
        for (int i = 0; i < M; i++) {
            if (!p[i].isOut) return false;
        }
        return true;
    }

    private static void rotateRect() {
        //맵 복사
        copy = new int[N][];
        for (int i = 0; i < N; i++) {
            copy[i] = Arrays.copyOfRange(map[i], 0, N);
        }

        //복사한 값을 원본에 돌려서 넣기
        for (int i = bx, x = by; i < bx + boxSize; i++, x++) {
            for (int j = by, y = bx + boxSize - 1; j < by + boxSize; j++, y--) {
                map[i][j] = copy[y][x];

                //내구도 감소
                if (isArea(map[i][j], 1, 10))
                    map[i][j]--;
            }
        }

        //출구 위치 변경
        if (isArea(exit.x, bx, bx + boxSize) && isArea(exit.y, by, by + boxSize)) {
            //(0,0) 기준으로 옮김
            int nx = exit.x - bx;
            int ny = exit.y - by;

            //회전시킴
            //20 -> 00
            //10 -> 01
            //00 -> 02
            //[x][y] -> [y][size-x-1]
            exit.x = ny + bx;
            exit.y = boxSize - nx - 1 + by;
        }

        //사람 위치 변경
        for (int i = 0; i < M; i++) {
            if (p[i].isOut) continue;

            if (isArea(p[i].x, bx, bx + boxSize) && isArea(p[i].y, by, by + boxSize)) {
                int nx = p[i].x - bx;
                int ny = p[i].y - by;

                p[i].x = ny + bx;
                p[i].y = boxSize - nx - 1 + by;
            }
        }
    }

    private static void findRect() {
        for (int size = 2; size <= N; size++) { //만들 수 있는 사각형
            for (int i = 0; i < N - size + 1; i++) {
                for (int j = 0; j < N - size + 1; j++) {
                    //출구가 있는지 확인
                    if (!(isArea(exit.x, i, i + size) && isArea(exit.y, j, j + size))) {
                        continue;
                    }

                    boolean flag = false;
                    //사람이 있는지 확인
                    for (int m = 0; m < M; m++) {
                        if (p[m].isOut) continue; //출구에 있는 참가자 제외

                        Pos now = p[m];
                        if (i <= now.x && now.x < i + size
                                && j <= now.y && now.y < j + size) {
                            flag = true;
                        }
                    }

                    if (flag) {
                        bx = i;
                        by = j;
                        boxSize = size;
                        return;
                    }

                }//end j

            }//end i

        }//end size
    }

    private static void movePeople(int idx) {
        Pos now = p[idx];

        //이미 출구인 경우
        if (now.isOut) return;

        //행이 다르다면 상하로 움직이기
        if (now.x != exit.x) {
            int nx = now.x;
            int ny = now.y;

            if (nx > exit.x) nx--; //위로 이동
            else nx++; //아래로 이동

            if (isRange(nx, ny) && map[nx][ny] == 0) {
                //움직일 수 있음
                now.x = nx;
                now.y = ny;
                p[idx] = now;
                total++;
                return;
            }
        }

        //열이 다르다면 좌우로 움직이기
        if (now.y != exit.y) {
            int nx = now.x;
            int ny = now.y;

            if (ny > exit.y) ny--; //좌로 이동
            else ny++; //우로 이동

            if (isRange(nx, ny) && map[nx][ny] == 0) {
                now.x = nx;
                now.y = ny;
                p[idx] = now;
                total++;
            }
        }
    }

    private static boolean isArea(int x, int min, int max) {
        if (min <= x && x < max) return true;
        return false;
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N) return false;
        return true;
    }
}

문제 링크

https://www.codetree.ai/training-field/search/a-train-that-goes-together/description?page=1&pageSize=20&username= 

접근 방법

위치가 증가하는 순서로 주어졌기 때문에 배열의 뒤에서부터 탐색한다.

열차의 속도가 같거나 작은 경우는 따라잡지 못하고, 큰 경우에는 따라잡을 수 있다.

반복문을 돌면서 가장 끝 위치의 속도를 저장하고 이 속도보다 작거나 같은 경우 만날 수 없기 때문에 결과값 증가, 열차의 속도를 현재 배열 값으로 갱신한다.

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N];

        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            Integer.parseInt(tokens.nextToken());
            int speed = Integer.parseInt(tokens.nextToken());

            arr[i] = speed;
        }

        int res = 1;
        int min = arr[N - 1];

        for (int i = N - 2; i >= 0; i--) {
            if(arr[i] <= min){
                res++;
                min = arr[i];
            }
        }

        System.out.println(res);

    }
}

문제 링크

https://www.codetree.ai/training-field/search/milk-production-competition/description?page=3&pageSize=20&username=

접근 방법

• 100일 만큼의 크기인 days 배열에 소의 이름과 등락값 저장
• 100일만큼 반복문을 돌면서 우유의 등락값 계산
• 우유의 최대값을 계산하고 임시 전광판 배열인 temp에서 최대값으로 우유를 생산한 소의 전광판만 1로 표시해줌
• 이전 전광판과 비교해서 달라졌다면 res++
• 전광판 갱신

코드

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

public class Main_우유생산량경쟁 {

    static final StringB= "Bessie";
    static final StringE= "Elsie";
    static final StringM= "Mildred";

    static class Cows{
        String name;
        int upDown;

        public Cows(String name, int upDown) {
            this.name = name;
            this.upDown = upDown;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens;

        int N = Integer.parseInt(br.readLine());
        Cows[] days = new Cows[101];

        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());

            int day = Integer.parseInt(tokens.nextToken());
            String cow = tokens.nextToken();
            int upDown = Integer.parseInt(tokens.nextToken());

            days[day] = new Cows(cow, upDown);
        }

        //가장 처음 날짜는 7갤런씩, 3마리 모두 전광판에 이름을 올림
        int res = 0;
        int[] score = new int[]{7, 7, 7};
        int[] prev = new int[]{1, 1, 1};

        for (int i = 0; i <= 100; i++) {
            if(days[i] == null) continue;

            //우유 등락 계산
            if(days[i].name.equals(B)){
                score[0] += days[i].upDown;
            } else if (days[i].name.equals(E)) {
                score[1] += days[i].upDown;
            }else {
                score[2] += days[i].upDown;
            }

            //최대값 구하기
            int max = Math.max(score[0], Math.max(score[1], score[2]));

            //전광판에 올라갈 최대값만 저장
            int[] temp = new int[3];
            for (int j = 0; j < 3; j++) { //최대값만 저장
                if(score[j] == max) temp[j] = 1;
            }

            //이전 전광판이랑 비교해서 달라졌는지 확인
            boolean flag = false;
            for (int j = 0; j < 3; j++) {
                if(prev[j] != temp[j]) flag = true;
            }
            if(flag) res++;

            //전광판 갱신
            prev = Arrays.copyOf(temp, 3);
        }
        System.out.println(res);
    }
}

문제 링크

https://www.codetree.ai/training-field/search/specific-alphabet-of-two-words/submissions?page=3&pageSize=20&username=

접근 방법

한 행에 대해서 양 옆의 문자 중 서로 다른 단어가 나오면 그 단어의 카운트를 집계, 같은 단어가 나온다면 가장 많이 나온 횟수를 갱신하는 것이었다.

문제 이해하는데 시간이 오래 걸려서 스터디원의 도움을 받았다.

fox box의 경우는 f, b 경우에는 겹치지 않기 때문에 1을 추가. o와 x는 둘 다 최대 1번씩 나타나기 때문에 1씩 갱신해준다

bus car의 경우에는 b는 한번 등장했기에 위에서 +1을 해줘서 총 2가 되고, 나머지의 경우도 1로 갱신이 된다.

코드

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

public class Main_두단어중특정알파벳 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        int[] res = new int[26];
        int[] cnt1, cnt2;

        String left, right;

        for (int i = 0; i < T; i++) {
            StringTokenizer tokens = new StringTokenizer(br.readLine());
            left = tokens.nextToken();
            right = tokens.nextToken();

            cnt1 = new int[26];
            cnt2 = new int[26];

            for (int j = 0; j < left.length(); j++) {
                cnt1[left.charAt(j)-'a']++;
            }
            for (int j = 0; j < right.length(); j++) {
                cnt2[right.charAt(j)-'a']++;
            }

            for (int j = 0; j < 26; j++) {
                res[j] += Math.max(cnt1[j], cnt2[j]);
            }

        }

        for (int i = 0; i < 26; i++) {
            bw.write(res[i]+"\n");
        }
        bw.flush();
        bw.close();

    }
}

문제 링크

https://www.codetree.ai/training-field/search/specific-alphabet-of-two-words/description?page=1&pageSize=20&username=

접근 방법

a, b, c와 세 수를 각각 곱한 값 7개를 만든다

리스트에 담아 큰 수 먼저 정렬, 그 다음으로 홀수를 정렬

정렬을 2번 하는 것이 비효율적이라 생각이 들었다.

스터디원의 얘기를 들어보니 홀수가 없다면 전부 곱하고, 홀수가 있다면 홀수만 계산하는 방법을 선택했다고 한다.

코드

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

public class Main_수의곱셈 {

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

        StringTokenizer tokens = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(tokens.nextToken());
        int b = Integer.parseInt(tokens.nextToken());
        int c = Integer.parseInt(tokens.nextToken());

        ArrayList<Integer> list = new ArrayList<>();
        list.add(a);
        list.add(b);
        list.add(c);
        list.add(a * b);
        list.add(a * c);
        list.add(b * c);
        list.add(a * b * c);

        //큰 수 정렬
        Collections.sort(list, Collections.reverseOrder());

        //홀수 정렬
        Collections.sort(list, ((x, y) ->{
            if(x%2==1 && y%2==0){
                return x-y;
            }
            return y-x;
        }));

        System.out.println(list.get(0));

    }

}

문제 링크

https://www.codetree.ai/training-field/frequent-problems/codetree-mon-bread/description?page=3&pageSize=20&username= 

접근 방법

위치 배열을 2차원 배열로 사용했다. [사람수][편의점/현위치]

한번 이동할때마다 이 사람이 베이스캠프에 배정되어야 하는지, 편의점에 도착했는지를 확인해야 한다.

자기 차례가 현재 시간보다 크면 더 이상 탐색할 필요가 없다.

이동할때에는 어느 방향으로 가야 하는지를 처음에 몰랐다. 스터디에서 bfs로 가야 하는 방향을 구하려면, 처음에 방향에 대한 값을 그대로 유지하면서 도착지까지 bfs로 구한다. 그래서 q에 넣을 때 처음 4방향이 범위에 맞고 갈 수 있는 방향인지 확인한 다음 큐에 모두 넣었다.

이 부분을 생각하지 못해서(그리고 그 외 코드 오류의 이유로) 44%에서 시간 초과가 났으나 결국 고쳤다!

편의점에 도착했는지 확인할 때,

if (pos[i][0].x == pos[i][1].x && pos[i][0].y == pos[i][1].y)

if (pos[i][0] == pos[i][1])

이 두개가 같은 동작이 되는 줄 알고 후자로 썼다가 메모리 초과가 생겼다. 자바에서 객체에 대한 비교는 메모리 주소를 비교하기 때문에 땡!

또한, 처음에는 베이스캠프를 전부 구해두고 시작하려 했는데 다른 부분과 겹쳐져 오류가 났다. 베이스캠프를 전부 구하고 시작해도 되는지 궁금하다. 다음에 시간이 날 때 한번 풀어봐야겠다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    static int N, M, map[][], finish;
    static Pos pos[][];
    static int[][] dir = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}};

    static class Pos {
        int x, y, d;

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

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

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(br.readLine());

        //입력 받기
        N = Integer.parseInt(tokens.nextToken()); //격자 크기
        M = Integer.parseInt(tokens.nextToken()); //사람 수
        map = new int[N][N]; //맵
        pos = new Pos[M][2]; //편의점 위치, 현재 위치

        //map input
        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
            }
        }

        //store input
        for (int i = 0; i < M; i++) {
            tokens = new StringTokenizer(br.readLine());
            pos[i][0] = new Pos(Integer.parseInt(tokens.nextToken()) - 1, Integer.parseInt(tokens.nextToken()) - 1);
        }

        int t = 0;
        finish = 0;
        while (finish < M) {
            move(t++);
        }
        System.out.println(t);

    }

    private static void move(int t) {
        //한 타임마다 모든 사람 이동
        for (int i = 0; i < M; i++) {
            //자기 차례가 되지 않아 격자 밖이라면 더이상 진행 안함
            if (i > t) return;
            //t == i이고 pos 현위치가 null이라면 베이스캠프 배정
            if (i == t && pos[i][1] == null) {
                getBaseCamp(i); //i번째 사람이 가려는 편의점에서 가장 가까운 베이스캠프 정함
            } else { //아니라면 최단 거리로 갈 방향 선택해서 이동
                if(pos[i][1] == null) continue; //이미편의점에 도착한 사람
                int d = goFast(i); //최단 거리로 갈 방향 구해옴
                //이동
                pos[i][1].x += dir[d][0];
                pos[i][1].y += dir[d][1];
                //편의점에 도착했는지 확인
                if (pos[i][0].x == pos[i][1].x && pos[i][0].y == pos[i][1].y) {
                    int cx = pos[i][0].x;
                    int cy = pos[i][0].y;
                    map[cx][cy] = 9; //맵에 방문 못하게 처리
                    pos[i][1] = null; //자신은 비움
                    finish++; //편의점에 도착한 사람 처리
                }
            }

        }

    }

    private static int goFast(int idx) { //현위치
        //현 위치에서 목적지 편의점까지 가장 빠른 방향을 구함
        Pos dest = pos[idx][0]; //도착하고자 하는 곳
        Pos start = pos[idx][1]; //현재 위치
        Deque<Pos> q = new ArrayDeque<>();
        boolean[][] v = new boolean[N][N];

        //4방향 전부 넣음
        for (int d = 0; d < 4; d++) {
            int nx = start.x + dir[d][0];
            int ny = start.y + dir[d][1];
            if(!isRange(nx, ny) || map[nx][ny] == 9) continue;
            q.offer(new Pos(nx, ny, d));
            v[nx][ny] = true;
        }

        int direction = -1;

        while (!q.isEmpty()) {
            Pos cur = q.poll();
            if (cur.x == dest.x && cur.y == dest.y) {
                //목적지 방향을 구함
                direction = cur.d;
                break;
            }

            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dir[d][0];
                int ny = cur.y + dir[d][1];

                if (!isRange(nx, ny) || map[nx][ny] == 9 || v[nx][ny]) continue;
                q.offer(new Pos(nx, ny, cur.d)); //방향 처음 그대로 저장
                v[nx][ny] = true;
            }
        }
        return direction;
    }

    //베이스 캠프 정하기 : bfs, 주어진 방향 순서대로 이동 후 가장 먼저 도착하는 곳이 베이스캠프(상좌우하)
    private static void getBaseCamp(int idx) {
        Pos s = pos[idx][0];
        Deque<Pos> q = new ArrayDeque<>();
        q.offer(s);
        boolean[][] v = new boolean[N][N];
        v[s.x][s.y] = true;

        while (!q.isEmpty()) {
            Pos cur = q.poll();

            for (int d = 0; d < 4; d++) {
                int nx = cur.x + dir[d][0];
                int ny = cur.y + dir[d][1];

                if (!isRange(nx, ny) || map[nx][ny] == 9 || v[nx][ny]) continue;
                //0이면 다음 위치로
                if (map[nx][ny] == 0) {
                    q.offer(new Pos(nx, ny));
                    v[nx][ny] = true;
                }
                //1이면 베이스 캠프 선택 완료
                if (map[nx][ny] == 1) {
                    pos[idx][1] = new Pos(nx, ny); //현재 위치 갱신
                    map[nx][ny] = 9; //맵에서 사용 못하게 처리
                    return;
                }
            }
        }
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N) return false;
        return true;
    }

}

문제 링크

https://www.codetree.ai/training-field/frequent-problems/tail-catch-play/description?page=3&pageSize=20&username=nnindd&discussionRowsPerPage=5&discussionPage=1

접근 방법

큰 순서는 아래와 같다.

• 1의 위치를 리스트에 저장
• k번 게임 실행
  • 이동 (M만큼 for)
    • 바뀐 1의 위치 갱신
  • 공 던지는 4분면, 행, 열, 방향 구하기
  • 공 던지기
    • 맞음
      • 맞았다면 몇번째 사람인지 구하기
        • 맵의 크기만큼 반복문 돌면서 1인 곳 찾기
        • 1이면 해당 팀원 위치 리스트 받아오기
        • 그 리스트에 맞은 사람 위치 있는지 확인
        • 있으면 맵에서 1, 3 변경
        • 있으면 머리 리스트에서 1 위치 갱신
        • 인덱스 제곱 계산해서 반환
    • 안 맞음
      • 공 멈추기 않고 던지기

길다..
우욱..
깔끔하게 작성하려고 함수를 다 빼면서 작성하다가 헷갈려서 생각나는대로 적었다.
input이 적기 때문에 전부 확인해봐도 되었고, 시간복잡도는 O(K*N^2)라니 1000*20^2면.. 할만함

어려웠던 부분

공 던지는 위치를 구하는게 어려웠다.

일정한 크기에 대해서 지정을 하려면 % 연산이 필요하다는걸 알겠는데 어떻게 계산을 해야 할지 몰라서 처음엔 풀지 못했다.

일단 4분면 중 한곳에 위치할 수 있게 하고, 방향에 따라서 N 안에서 어디에 위치하는지...

/ 와 % 를 사용하면 된다는걸 아는데.. 아는데! 항상 헷갈린다..

더 많이 풀어봐야함

지나갈 수 있는 길이 1 2 2 3 4 4 4 이런 형식이 아니라 1 2 2 2 2 3 으로 끝나는 경우를 생각해봐야 한다.

1이 이동할 땐 4인 곳으로 가는 것이 아니라 2가 아닌 곳으로 간다고 생각해야 한다.

이 생각을 듣고 아득해짐......

코드

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

public class Main {

    static int N, M, K, map[][], total;
    static ArrayList<int[]> first; //1의 위치
    static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer tokens = new StringTokenizer(br.readLine());
        N = Integer.parseInt(tokens.nextToken()); //격자 크기
        M = Integer.parseInt(tokens.nextToken()); //팀의 개수
        K = Integer.parseInt(tokens.nextToken()); //라운드 수

        map = new int[N][N]; //맵
        total = 0;

        first = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            tokens = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(tokens.nextToken());
                if (map[i][j] == 1) { //1의 위치 저장
                    first.add(new int[]{i, j});
                }
            }
        }//end input

        for (int i = 0; i < K; i++) {
            total += play(i);
        }

        bw.write(total + "");
        bw.flush();
        bw.close();
    }

    private static int play(int k) {
        //이동
        for (int i = 0; i < M; i++) {
            int[] cur = move(first.get(i));
            //바뀐 1의 위치 갱신해주기
            first.set(i, cur);
        }

        //공던짐
        int[] rcd = getRowColDirection(k);
        int area = rcd[0];
        int row = rcd[1];
        int col = rcd[2];
        int d = rcd[3];

        int x = row;
        int y = col;
        int temp = 0;
        while (isRange(x, y)) { //범위 안 벗어날때까지
            if (map[x][y] != 0 && map[x][y] != 4) {
                //맞은 사람 몇번째인지 구하기 + 점수 갱신 + 머리 꼬리 바꾸기
                temp = checkIndex(x, y);
                break;
            }
            //안 맞았으면 다음방향
            x += dir[d][0];
            y += dir[d][1];
        }
        return temp;
    }

    private static int checkIndex(int x, int y) {
        //몇번째 사람인지 구하기

        ArrayList<int[]> list;

        //1인 부분 확인
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] != 1) continue;

                //이 팀원 리스트 불러옴
                list = getTeamPosition(new int[]{i, j});

                //이 팀원 중 이사람이 있는지 확인
                for (int k = 0; k < list.size(); k++) {
                    if (list.get(k)[0] == x && list.get(k)[1] == y) {
                        //머리 꼬리 맵에서 바꾸기
                        int[] front = list.get(0);
                        int[] back = list.get(list.size()-1);
                        int temp = map[front[0]][front[1]];
                        map[front[0]][front[1]] = map[back[0]][back[1]];
                        map[back[0]][back[1]] = temp;

                        //머리 리스트에 머리 변경
                        for (int l = 0; l < first.size(); l++) {
                            int[] head = first.get(l);
                            if(head[0] == front[0] && head[1] == front[1]){
                                first.set(l, back); //꼬리를 머리로 바꿈
                            }
                        }
                        //점수 반환
                        return (k + 1) * (k + 1);
                    }
                }
            }
        }
        return 0;
    }

    private static int[] getRowColDirection(int k) {
        //던진 위치에 따라서 행, 열, 방향을 구함
        // 좌 하 우 상 순서로 0 1 2 3
        int area, row, col, dir; //4변 중 위치, 어느 행/열에 있는지, 공던지는 방향

        area = (k / N) % 4; //4변 중 어디인지 구하기

        if (area == 0) {
            col = 0;
            row = k % N;
            dir = 3;
        } else if (area == 1) {
            row = N - 1;
            col = k % N;
            dir = 0;
        } else if (area == 2) {
            row = N - (k % N) - 1;
            col = N - 1;
            dir = 2;
        } else {
            row = 0;
            col = N - (k % N) - 1;
            dir = 1;
        }

        return new int[]{area, row, col, dir};
    }

    private static int[] move(int[] n1) {
        //팀원 리스트 구함
        ArrayList<int[]> list = getTeamPosition(n1);

        //한명씩 이동 -> 첫번째만 갈 곳 정하고 그 다음부턴 이전의 위치로 변경
        //첫번째 이동
        int[] one = n1;//첫번째가 이동한 위치 저장 (1이 3으로 이동했을 때 4로 덮어씌워지는것 방지)
        for (int d = 0; d < 4; d++) {
            int nx = n1[0] + dir[d][0];
            int ny = n1[1] + dir[d][1];

            //범위 내이고 2가 아닐때
            if (!isRange(nx, ny) || map[nx][ny] == 0) continue;
            if (map[nx][ny] != 2) {
                map[nx][ny] = map[n1[0]][n1[1]]; //1번은 0,2가 아닌 곳으로 이동
                one = new int[]{nx, ny};
                break; //더 볼 것 없음
            }
        }

        int[] next = n1; //다음 사람이 이동할 곳
        //남은 위치 이동
        for (int i = 1; i < list.size(); i++) {
            //위치 이동
            int[] cur = list.get(i);
            map[next[0]][next[1]] = map[cur[0]][cur[1]]; //앞의 사람이 옮겨간 자리에 채우기
            if (i == list.size() - 1) {
                map[next[0]][next[1]] = 3; //마지막 값이라면 1이 덮어씌운 값으로 들어가는 것 방지3 처리
            }
            map[cur[0]][cur[1]] = 4; //자신이 있던 곳 빈곳 처리
            next = cur; //다음 채울 곳 갱신
        }
        //1이 3으로 이동했을 때 마지막에 4로 덮어 씌워지는 것 방지
        map[one[0]][one[1]] = 1;

        //1의 위치 갱신
        return one;
    }

    private static ArrayList<int[]> getTeamPosition(int[] n1) {
        Queue<int[]> q = new ArrayDeque<>(); //방문확인
        q.offer(n1);
        boolean[][] v = new boolean[N][N];
        v[n1[0]][n1[1]] = true;
        ArrayList<int[]> list = new ArrayList<>(); //팀들 위치 저장 리스트
        list.add(n1);

        //bfs로 팀원 위치 구함
        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dir[d][0];
                int ny = cur[1] + dir[d][1];

                if (!isRange(nx, ny) || map[nx][ny] == 0 || map[nx][ny] == 4 || v[nx][ny]) continue;
                //나의 값보다 같거나 하나 클때만 이동
                if ((map[cur[0]][cur[1]] == 1 && map[nx][ny] == 2)
                        || (map[cur[0]][cur[1]] == 2 && map[cur[0]][cur[1]] <= map[nx][ny])) {
                    //1이면 2로만 가고, 2라면 같거나 큰곳으로만
                    v[nx][ny] = true;
                    q.offer(new int[]{nx, ny});
                    list.add(new int[]{nx, ny}); //팀원 위치 저장
                }
            }
        }
        return list;
    }

    private static boolean isRange(int x, int y) {
        if (x < 0 || y < 0 || x >= N || y >= N) return false;
        return true;
    }


}