座標圧縮について勉強した java

調べてもあまり引っかからなかったのでまとめておきます。

座標圧縮とは与えられる範囲は大きいが、全ての値を把握する必要はない場合（たとえば#で分けられた領域の数を数える問題など）に使えるテクニックです。

・・・・・・・・・・・・・＃・・

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

・・・・・・・・・＃＃＃・・・・

・・・・・・・・・＃＃＃・・・・

＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃＃

・・・・・＃・・・＃＃＃・・・・

・・・・＃＃＃・・＃＃＃・・・・

上に座標圧縮を使うと

・・・・・・・＃・

＃＃＃＃＃＃＃＃＃

・・・・・＃・・・

＃＃＃＃＃＃＃＃＃

・・＃・・＃・・・

・＃＃＃・＃・・・

のようになります。領域を潰さずにサイズを小さくできましたね。

大まかな手順

まず、x軸について圧縮します。

 ・・・・・・・・＃・

＃＃＃＃＃＃＃＃＃・

＃＃＃＃＃＃＃＃＃・

・＃・・・・・・＃・

０１２３４５６７８９ 

このような場合横に＃が続いているところをカットしたいのですが

それを実現するために、左側に＃の境界があるxをメモします

上の場合01289です

そして、セットに入っていない座標は無視して、01289の座標だけつなげます

こんな感じで。y軸についても同じことをして

圧縮できた

具体的な手順

01289を繋げて～とかいうのを具体的にどうやるか説明します。

壁(#)のある位置は複数の長方形で渡されており、左端の座標はx1に、右端の座標（半開区間）はx2の配列に格納されているものとします

この場合x1には{0,1,8} x2には{9,2,9}という風に入っています。

                         つまり0~9 ,1~2 ,8~9の３つが塗られている。

ここで、間の座標をカットするという事は使う数を小さい順に並べた01289で、8を3に,9を4にずらして、0からの順列にすることに他なりません。

つまり

x1{0,1,8} を {0 ,1 ,3}に

x2{9,2,9} を {4, 2 ,4}にしてやればx座標について圧縮した事になります(yも似た感じで)

・・・＃・

＃＃＃＃・

＃＃＃＃・

・＃・＃・

数をずらすにはTreeSetに0と右端、x1,x2の値をすべて入れて、前から何番目にあるかを調べれば良いです

参考問題

ペンキの色 | Aizu Online Judge

//座標を圧縮し、長さを返す
//W = compress(x1, x2, W);
//H = compress(y1, y2, H); みたいに使って圧縮する
    public static int compress(int[] x1, int[] x2, int w)
    {
        int n = x1.length;
         //自動でソートしてくれる
        TreeSet<Integer> set = new TreeSet<>();
        //両端を入れないと端の余白が消える     ...#.. が #  になる
        //                                  ...#..    #
        set.add(0);
        set.add(w);
        for (int i = 0; i < n; i++)
        {
            set.add(x1[i]);
            set.add(x2[i]);
        }
         int nw = set.size();
        Integer[] x = set.toArray(new Integer[nw]);
        for (int i = 0; i < n; i++)
        {
            //座標を前から何番目にあるかで入れ直す
            x1[i] = Arrays.binarySearch(x, x1[i]);
            x2[i] = Arrays.binarySearch(x, x2[i]);
        }
        return nw - 1; // | | | | の区切りがある時、長さは3
    }