[伯俊]監視

こんにちは!
今回のPostingは白俊の監視問題。と書きます

質問する

サマリ
地図には5つの監視カメラがある.
各モニタリングには独自のモニタリング方向があり、他のモニタリング領域はモニタリングを透過することができる.
ただし、壁を通過することはできません(6).
これは、監視できない死角領域の数を返す問題です.

初志

まず、5つの監視カメラをどのように処理するかを考えました.
モニタリング管理は3 Dアレイ管理を採用し,指向性処理を行った.0(빈 공간)と入力します.
これはシミュレーションの問題なので、手順に従って処理できれば、次のことができます:)

コードの説明

static int R, C, SIZE, min, cctv[][][];
static char map[][];
static List<Integer> cctvList;      // 맵에 존재하는 CCTV
static List<int[]> cctvLoc;         // cctvList와 인덱스를 동일하게 가져가며, CCTV의 위치를 저장

// 상 하 좌 우
static int[] dr = { -1, 1, 0, 0 };
static int[] dc = { 0, 0, -1, 1 };

Mainクラスに宣言されたクラス変数.
宣言入力値R, C, mapなど.
カメラが入ると、カメラの位置が格納されているリストを一緒に宣言しました.
CCTVの数が入力されていないため、サイズの柔軟なリストを使用し、周囲の方向を示すdr, dc配列を宣言しました.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
R = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());

入力は配列に入るので、バッファを使用して入力値を受け入れます.

private static void main(String[] args) {
    // ...
    cctvInit();
    // ...
}

// cctv의 번호마다 가능한 방향 인덱스를 저장함
private static void cctvInit() {
    cctv = new int[6][][];
    cctv[1] = new int[][]{ {0}, {1}, {2}, {3} };
    cctv[2] = new int[][]{ {0, 1}, {2, 3} };
    cctv[3] = new int[][]{ {0, 2}, {0, 3}, {1, 2}, {1, 3} };
    cctv[4] = new int[][]{ {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3} };
    cctv[5] = new int[][]{ {0, 1, 2, 3} };
}

次に、各番号の方向に合うように3 D配列を初期化します.
私は監視カメラを90度回転させることができるので、可能な方向をすべて保存しました.

map = new char[R][C];
cctvList = new ArrayList<>();
cctvLoc = new ArrayList<>();

// 맵 초기화 & 사각지대 체크 & cctv 좌표, 번호 저장
for (int i = 0; i < R; i++) {
    st = new StringTokenizer(br.readLine(), " ");
    for (int j = 0; j < C; j++) {
        char c = st.nextToken().charAt(0);
        if (c == '0') min++;
        else if (c != '6'){
            cctvList.add(Character.getNumericValue(c));     // 몇 번 CCTV인지 저장
            cctvLoc.add(new int[]{i, j});                   // 해당 CCTV의 좌표 저장
        }
        map[i][j] = c;
    }
}

map配列をRXCサイズに初期化し、入力値を受信して保存します.0と入力されている場合は空白です.min変数に追加します.
壁を示す6でない場合は、モニタ位置とモニタ回数を保存し、mapに追加します.

SIZE = cctvList.size();     // 재귀 기저조건인 SIZE 저장
watch(0, min, map);

すべての入力値が処理されると、watchメソッドが呼び出され、すべてのカメラの数が決定される.

private static void watch(int no, int cnt, char[][] currMap) {
    // 만약 CCTV SIZE만큼 확인하거나 빈 공간이 이미 없을 때 return
    if (no == SIZE || cnt == 0) {
        min = Math.min(cnt, min);
        return;
    }

    // 해당 CCTV가 위치한 좌표 (r,c)
    int r = cctvLoc.get(no)[0];
    int c = cctvLoc.get(no)[1];
    int[][] currCCTV = cctv[cctvList.get(no)];  // 해당 번호의 CCTV가 확인할 수 있는 방향을 가져옴

    // 방향이 여러개가 가능하면 하나씩 체크
    for (int i = 0; i < currCCTV.length; i++) {
        // 해당 CCTV가 감시한 영역을 체크할 배열 하나 더 선언 후 currMap 값을 copy
        char[][] temp = new char[R][C];
        for (int j = 0; j < R; j++) {
            System.arraycopy(currMap[j], 0, temp[j], 0, C);
        }

        int sum = 0;    // 감시할 수 있는 영역들의 합

        // 방향을 차례로 체크하면서 감시 가능한 모든 영역을 표시
        for (int j = 0; j < currCCTV[i].length; j++) {
            int d = currCCTV[i][j];     // 체크할 방향
            int nr = r + dr[d];         // next r
            int nc = c + dc[d];         // next c

            // 해당 좌표가 유효하고, 벽이 아니면 계속 반복 수행
            while (isValid(nr, nc) && temp[nr][nc] != '6') {
                // 만약 CCTV라면 continue
                if (temp[nr][nc] != '0' && temp[nr][nc] != '#') {
                    nr += dr[d];
                    nc += dc[d];
                    continue;
                }

                // 빈 공간이라면 sum - 1
                // #은 건너뜀
                if (temp[nr][nc] == '0') {
                    sum++;
                }
                temp[nr][nc] = '#';

                nr += dr[d];
                nc += dc[d];
            }
        }

        // 다음 CCTV 재귀호출
        watch(no+1, cnt-sum, temp);
    }

}

watchメソッドは、すべての監視可能な位置で#をチェックし、呼び出しを返すメソッドである.noはチェックするモニタ番号であり、cntはこれまでの空き領域であり、currMapは再帰呼び出し時に変更された状態mapである.
クラス変数はもともとmapであるため、伝達配列を減少させ、配列を返すパラメータを返します.
(以下、方法をより詳細に説明する)

// 만약 CCTV SIZE만큼 확인하거나 빈 공간이 이미 없을 때 return
if (no == SIZE || cnt == 0) {
    min = Math.min(cnt, min);
    return;
}

呼び出したモニタの数(すべてのモニタを考慮)またはスペースが存在しない場合、再帰関数は終了します.

// 해당 CCTV가 위치한 좌표 (r,c)
int r = cctvLoc.get(no)[0];
int c = cctvLoc.get(no)[1];
int[][] currCCTV = cctv[cctvList.get(no)];  // 해당 번호의 CCTV가 확인할 수 있는 방향을 가져옴

既存の条件を満たしていない場合は、現在のパラメータを入力したカメラが座標を取得し、現在のカメラが表示できる方向を入力します.

// 방향이 여러개가 가능하면 하나씩 체크
for (int i = 0; i < currCCTV.length; i++) {
    // 해당 CCTV가 감시한 영역을 체크할 배열 하나 더 선언 후 currMap 값을 copy
    char[][] temp = new char[R][C];
    for (int j = 0; j < R; j++) {
        System.arraycopy(currMap[j], 0, temp[j], 0, C);
    }

    int sum = 0;    // 감시할 수 있는 영역들의 합

    // 방향을 차례로 체크하면서 감시 가능한 모든 영역을 표시
    for (int j = 0; j < currCCTV[i].length; j++) {
        int d = currCCTV[i][j];     // 체크할 방향
        int nr = r + dr[d];         // next r
        int nc = c + dc[d];         // next c

        // 해당 좌표가 유효하고, 벽이 아니면 계속 반복 수행
        while (isValid(nr, nc) && temp[nr][nc] != '6') {
            // 만약 CCTV라면 continue
            if (temp[nr][nc] != '0' && temp[nr][nc] != '#') {
                nr += dr[d];
                nc += dc[d];
                continue;
            }

            // 빈 공간이라면 sum - 1
            // #은 건너뜀
            if (temp[nr][nc] == '0') {
                sum++;
            }
            temp[nr][nc] = '#';

            nr += dr[d];
            nc += dc[d];
        }
    }
    // 다음 CCTV 재귀호출
    watch(no+1, cnt-sum, temp);
}

currCCTV.lengthのドアは、現在のモニタリングで可能なすべての方向を確認する必要があるためです.
モニタモニタが監視する方向を検出する場合、配列を変更する必要があるため、temp配列を宣言し、パラメータとして入力されたcurrMap配列をコピーします.
監視可能な方向を順次確認し、すべての監視可能領域を#として表示します.6ではなく、0および#の場合、これらはすべてCCTV領域であるため、重複文は表示されない.
上記でない場合、表示continueは利用可能な空白を示し、#を処理する.
現在のモニタの可能な方向をすべて確認した場合は、sum++を再呼び出して、すべての状況のナビゲーションを完了します.

// 좌표의 유효성을 체크하는 메소드
private static boolean isValid(int r, int c) {
    if (r<0 || r>=R || c<0 || c>=C) return false;
    return true;
}

座標がwatchから離れているかどうかを確認する方法は簡単です.

完全なコード

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

public class Main {

    static int R, C, SIZE, min, cctv[][][];
    static char map[][];
    static List<Integer> cctvList;      // 맵에 존재하는 CCTV
    static List<int[]> cctvLoc;         // cctvList와 인덱스를 동일하게 가져가며, CCTV의 위치를 저장

    // 상 하 좌 우
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) throws IOException {
        // 입력이 배열이므로 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        cctvInit();             // 각 CCTV가 감시할 수 있는 방향을 저장하는 cctv 배열을 초기화
        map = new char[R][C];
        cctvList = new ArrayList<>();
        cctvLoc = new ArrayList<>();

        // 맵 초기화 & 사각지대 체크 & cctv 좌표, 번호 저장
        for (int i = 0; i < R; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < C; j++) {
                char c = st.nextToken().charAt(0);
                if (c == '0') min++;
                else if (c != '6'){
                    cctvList.add(Character.getNumericValue(c));     // 몇 번 CCTV인지 저장
                    cctvLoc.add(new int[]{i, j});                   // 해당 CCTV의 좌표 저장
                }
                map[i][j] = c;
            }
        }
        SIZE = cctvList.size();     // 재귀 기저조건인 SIZE 저장
        watch(0, min, map);

        System.out.println(min);
    }

    // 감시할 수 있는 위치에 # 체크 후 재귀
    private static void watch(int no, int cnt, char[][] currMap) {
        // 만약 CCTV SIZE만큼 확인하거나 빈 공간이 이미 없을 때 return
        if (no == SIZE || cnt == 0) {
            min = Math.min(cnt, min);
            return;
        }

        // 해당 CCTV가 위치한 좌표 (r,c)
        int r = cctvLoc.get(no)[0];
        int c = cctvLoc.get(no)[1];
        int[][] currCCTV = cctv[cctvList.get(no)];  // 해당 번호의 CCTV가 확인할 수 있는 방향을 가져옴

        // 방향이 여러개가 가능하면 하나씩 체크
        for (int i = 0; i < currCCTV.length; i++) {
            // 해당 CCTV가 감시한 영역을 체크할 배열 하나 더 선언 후 currMap 값을 copy
            char[][] temp = new char[R][C];
            for (int j = 0; j < R; j++) {
                System.arraycopy(currMap[j], 0, temp[j], 0, C);
            }

            int sum = 0;    // 감시할 수 있는 영역들의 합

            // 방향을 차례로 체크하면서 감시 가능한 모든 영역을 표시
            for (int j = 0; j < currCCTV[i].length; j++) {
                int d = currCCTV[i][j];     // 체크할 방향
                int nr = r + dr[d];         // next r
                int nc = c + dc[d];         // next c

                // 해당 좌표가 유효하고, 벽이 아니면 계속 반복 수행
                while (isValid(nr, nc) && temp[nr][nc] != '6') {
                    // 만약 CCTV라면 continue
                    if (temp[nr][nc] != '0' && temp[nr][nc] != '#') {
                        nr += dr[d];
                        nc += dc[d];
                        continue;
                    }

                    // 빈 공간이라면 sum - 1
                    // #은 건너뜀
                    if (temp[nr][nc] == '0') {
                        sum++;
                    }
                    temp[nr][nc] = '#';

                    nr += dr[d];
                    nc += dc[d];
                }
            }

            // 다음 CCTV 재귀호출
            watch(no+1, cnt-sum, temp);
        }

    }

    // 좌표의 유효성을 체크하는 메소드
    private static boolean isValid(int r, int c) {
        if (r<0 || r>=R || c<0 || c>=C) return false;
        return true;
    }

    // cctv의 번호마다 가능한 방향 인덱스를 저장함
    private static void cctvInit() {
        cctv = new int[6][][];
        cctv[1] = new int[][]{ {0}, {1}, {2}, {3} };
        cctv[2] = new int[][]{ {0, 1}, {2, 3} };
        cctv[3] = new int[][]{ {0, 2}, {0, 3}, {1, 2}, {1, 3} };
        cctv[4] = new int[][]{ {0, 1, 2}, {0, 1, 3}, {0, 2, 3}, {1, 2, 3} };
        cctv[5] = new int[][]{ {0, 1, 2, 3} };
    }

}

の最後の部分

副題トレーニングの過程で、私が一番嫌いなシミュレーション(実装)タイプをたくさん試しました.
よく、解が多すぎて、やはり好きではありませんが、解のスピードと精度が少し上がったようなので、わけがわからず喜んでいます:)