回転マトリクス枠線[テスト符号化]

15478 ワード

[問題リンク]
行x columnsサイズのマトリクス.行列の数字は1からrows x columnsの順に1行です.この行列で長方形の範囲を複数回選択し、枠線部分の数値を時計回りに回転させます.各回転は4つの整数(x 1、y 1、x 2、y 2)で表され、その意味は以下の通りである.
  • x 1行y 1列からx 2行y 2列に対応する領域の矩形では、枠の数字を時計回りに回転させる.
  • 行列の縦長(行数)行、横長(列数)列、および回転リストをクエリーする場合は、各回転を配列に適用し、回転位置によって変更された数値の最小値を配列に順番に戻して解く関数を完了します.
  • 制限
  • 行は2または100以下の自然数です.
  • 列は2以上100以下の自然数です.
  • が始まると、行列には1から1までの横方向の数字が増えていると書かれています.
  • 、すなわち、回転がない場合、i行j列の数字は(i-1)x columns+jとなる.
  • クエリのロー数(回転数)は10000より大きい.
  • クエリの各ローは、4つの整数[x 1、y 1、x 2、y 2]である.
  • x 1行のy 1列からx 2行のy 2列まで時計回りに領域の枠を回転させる.
  • 1≦x 1すべての回転は順番に行われます.
  • 例えば、2番目の回転の答えは、1番目の回転を実行し、その状態で2番目の回転を実行したときに、移動する数字の最大値を求めることである.
  • I/O例
  • rowscolumnsqueriesresult66[[2,2,5,4],[3,3,6,6],[5,1,6,3]][8, 10, 25]33[[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]][1, 1, 5, 3]10097[[1,1,100,97]][1]

    -完全なコード

    import java.util.*;
    
    class Solution {
        public int[] solution(int rows, int columns, int[][] queries) {
            int[] answer = new int[queries.length];
            int[][] matrix = new int[rows][columns];
            int count = 1;
            
            // 행렬 초기화
            for(int x = 0 ; x < rows ; x++) {
                for(int y = 0 ; y < columns ; y++) {
                    matrix[x][y] = count++;
                }
            }
            // answer에 사용될 count로 초기화
            count = 0;
            
            for(int[] i : queries) {
                // 회전좌표를 받아옴
                int x1 = i[0]-1;
                int y1 = i[1]-1;
                int x2 = i[2]-1;
                int y2 = i[3]-1;
                // 회전하기 전 첫 번째 값을 임시로 저장
                int temp = matrix[x1][y1];
                // 회전하는 숫자들 중 가장 작은 값을 찾기 위한 TreeSet
                TreeSet<Integer> set = new TreeSet<>();
                
                // (x1, y1) ~ (x2, y1) 까지 회전 (회전하는 사각형의 왼쪽)
                for(int x = x1 ; x < x2 ; x++) {
                    matrix[x][y1] = matrix[x+1][y1];
                    set.add(matrix[x][y1]);
                }
                // (x2, y1) ~ (x2, y2) 까지 회전 (회전하는 사각형의 아래쪽)
                for(int y = y1 ; y < y2 ; y++) {
                    matrix[x2][y] = matrix[x2][y+1];
                    set.add(matrix[x2][y]);
                }
                // (x2, y2) ~ (x1, y2) 까지 회전 (회전하는 사각형의 오른쪽)
                for(int x = x2 ; x > x1 ; x--) {
                    matrix[x][y2] = matrix[x-1][y2];
                    set.add(matrix[x][y2]);
                }
                // (x1, y2) ~ (x1, y1+1) 까지 회전 (회전하는 사각형의 위쪽)
                // (x1, y1+1)은 첫 번째 값을 받아오므로 temp를 저장
                // 회전으로 인해 첫 번째 값 위치에 이미 회전한 숫자가 배치되었기때문
                for(int y = y2 ; y > y1+1 ; y--) {
                    matrix[x1][y] = matrix[x1][y-1];
                    set.add(matrix[x1][y]);
                }
                matrix[x1][y1+1] = temp;
                set.add(matrix[x1][y1+1]);
                answer[count++] = set.first();
            }
            
            return answer;
        }
    }

    -詰まった場所&解決策


    行列の回転は、数字ごとにスペースを移動します.

    問題図の説明を参照して、マトリクスの左、下、右、上の枠線をそれぞれ1つの配列と見なして問題を解決します.各枠線配列では、次のセルの値が現在のセルの値としてインポートされ、最後のセルの値がtempという一時記憶変数からインポートされます.各枠線はツリーセットでループされ、値はツリーセットに格納され、格納されたツリーセットの最初の値が最大値になります.

    -感じる


    最初からすべての回転を実施するよりも,各フレームを分離して回転を実現することで,より容易に解くことができる.