挑战程序竞赛系列（34）：3.2坐标离散化

详细代码可以fork下Github上leetcode项目，不定期更新。

练习题如下：

AOJ 0531: Paint Color

AOJ 0531: Paint Color

坐标离散化，说白了，求解答案与给定的空间大小无关，那么可以对坐标进行压缩。就拿这道题而言，求的是所有未涂色的区域块，而给定的木板坐标远小于W和H，可以采用离散化技巧，离散可以简单理解为排序后输出相对大小。

接着，给定坐标范围我们就可以在二维空间内填充木板了，这里采用IMOS法，具体可以参考博文：http://www.hankcs.com/program/algorithm/imos_method.html，写的相当详细，不过对于二维的IMOS法，可以简单理解为：

对起点产生一个冲击，为正，在右上和左下分别产生两个负冲击，因为IMOS是做横向和纵向累计的，效应的传递过程中，当超出边界时，需要有相互抵消的力。自然地，右下为正，需要抵挡来自右上和左下负的冲击波，这种动态的更新过程是IMOS的精髓，尤其是当出现多个重复区域的木板在一个二维空间内的累加时，是非常节约时间的。

木板填充完毕后，可以采用BFS或者DFS来遍历连通的空白区域块，并计数。

代码如下：

代码语言：javascript复制

import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.TreeSet;

public class Main{
    InputStream is;
    PrintWriter out;
    String INPUT = "./data/judge/201708/A0531.txt";


    void solve() {
        while (true){
            int W = in.nextInt();
            int H = in.nextInt();
            if (W == 0 &&  H == 0) break;
            int N = in.nextInt();
            int MAX_N = N   16;
            X1 = new int[MAX_N];
            X2 = new int[MAX_N];
            Y1 = new int[MAX_N];
            Y2 = new int[MAX_N];
            for (int i = 0; i < N;   i){
                X1[i] = in.nextInt();
                Y1[i] = in.nextInt();
                X2[i] = in.nextInt();
                Y2[i] = in.nextInt();
            }

            W = compress(X1, X2, W);
            H = compress(Y1, Y2, H);

            int[][] fld = new int[2 * MAX_N][2 * MAX_N];

            //imos法
            for (int i = 0; i < N;   i){
                fld[Y1[i]][X1[i]]   ;
                fld[Y1[i]][X2[i]] --;
                fld[Y2[i]][X1[i]] --;
                fld[Y2[i]][X2[i]]   ;
            }

            //横向积
            for (int i = 0; i < H;   i){
                for (int j = 1; j < W;   j){
                    fld[i][j]  = fld[i][j - 1];
                }
            }

            //纵向积
            for (int j = 0; j < W;   j){
                for (int i = 1; i < H;   i){
                    fld[i][j]  = fld[i - 1][j];
                }
            }

            System.out.println(bfs(fld, W, H));

        }
    }

    int[][] dir = {{1, 0},{-1, 0},{0, -1},{0, 1}};

    class Pair{
        int x;
        int y;
        public Pair(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    int bfs(int[][] fld, int W, int H){
        Queue<Pair> queue = new LinkedList<>();
        int cnt = 0;
        for (int i = 0; i < H;   i){
            for (int j = 0; j < W;   j){
                if (fld[i][j] == 0){
                    cnt   ;
                    queue.offer(new Pair(i, j));
                    fld[i][j] = 1;
                    while (!queue.isEmpty()){
                        Pair now = queue.poll();
                        int x = now.x;
                        int y = now.y;
                        //fld[x][y] = 1;
                        for (int[] d : dir){
                            int nx = x   d[0];
                            int ny = y   d[1];
                            if (nx >= 0 && nx < H && ny >= 0 && ny < W && fld[nx][ny] == 0){
                                queue.offer(new Pair(nx, ny));
                                fld[nx][ny] = 1;
                            }
                        }
                    }
                }
            }
        }
        return cnt;
    }

    /*****************坐标离散化*******************/
    int[] X1;
    int[] X2;
    int[] Y1;
    int[] Y2;

    int compress(int[] x1, int[] x2, int w) {
        int n = x1.length;
        TreeSet<Integer> set = new TreeSet<Integer>();
        set.add(0);
        set.add(w);
        for (int i = 0; i < n;   i){
            set.add(x1[i]);
            set.add(x2[i]);
        }

        Integer[] x = set.toArray(new Integer[0]);
        for (int i = 0; i < n;   i){
            x1[i] = Arrays.binarySearch(x, x1[i]);
            x2[i] = Arrays.binarySearch(x, x2[i]);
        }

        return x.length - 1;
    }

    Scanner in;
    public Main(){
        in = new Scanner(System.in);
    }

    public static void main(String[] args) throws Exception {
        new Main().solve();
    }
}

github dfs fork leetcode paint

0 人点赞