SRM 396 Div1 Medium: FixImage

問題

白('.')と黒('#')のピクセルで構成されたテーブル(alteredImage)が与えられる。黒のピクセル同士が上下左右のいずれかで接しているとき、それらのピクセルは連結しているとする。連結した黒のピクセルの中から任意の2点を選んだとき、その2点のパスの長さがマンハッタン距離と等しくなるようなテーブルに変換したい。

できる操作は白のピクセルを黒のピクセルに変換することのみ。最小の操作回数で変換を行ったテーブルを求めよ。

制約

解法

コの字やロの字のようになっている連結した黒のピクセルは、任意の2点でパスの長さとマンハッタン距離が一致しないので、このような部分を探して変換する。黒のピクセル同士が連結しているかどうかはUnion Find Treeで管理する。

ある黒のピクセルAから上下左右の4方向を探索していき、白のピクセルを挟んでAと連結している黒のピクセルBを見つけたら、AとBの間の白のピクセルをすべて黒に変換する。これを全ピクセルに対して行い、更新が止まるまで続ける。

黒に変換することによって、違う塊だった黒ピクセル同士が連結することがあり得るので、変換操作の度に連結処理を行う。

import java.util.*;

public class FixImage {

    DisjointSet ds;
    char[][] pixel;
    int h, w;
    int[] dy = {0,1,0,-1};
    int[] dx = {1,0,-1,0};


    public String[] originalImage(String[] alteredImage) {
        h = alteredImage.length;
        w = alteredImage[0].length();

        pixel = new char[h][];
        for (int i=0; i<h; i++) pixel[i] = alteredImage[i].toCharArray();

        ds = new DisjointSet(h*w);

        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {

                if (pixel[i][j] == '.') continue;

                for (int k=0; k<2; k++) {
                    int ni = i + dy[k];
                    int nj = j + dx[k];
                    if (ni < 0 || nj < 0 || h <= ni || w <= nj || pixel[ni][nj] == '.') continue;

                    ds.unite(i*w+j, ni*w+nj);
                }
            }
        }

        boolean flag = true;

        while (flag) {
            flag = false;
            for (int i=0; i<h; i++) {
                for (int j=0; j<w; j++) {
                    if (pixel[i][j] == '.') continue;

                    for (int k=0; k<4; k++) {
                        int ni = i + dy[k];
                        int nj = j + dx[k];
                        if (ni < 0 || nj < 0 || h <= ni || w <= nj) continue;
                        if (pixel[ni][nj] == '#') continue;
                        if (check(ni, nj, dy[k], dx[k], i*w+j)) {
                            flag = true;
                        }
                    }
                }
            }
        }

        String[] res = new String[h];
        for (int i=0; i<h; i++) {
            res[i] = new String(pixel[i]);
        }
        return res;
    }


    boolean check(int i, int j, int di, int dj, int s) {
        if (i < 0 || j < 0 || h <= i || w <= j) return false;
        if (pixel[i][j] == '#') {
            if (ds.same(s, i*w+j)) return true;
            else return false;
        }

        if (check(i+di, j+dj, di, dj, s)) {
            pixel[i][j] = '#';
            for (int k=0; k<4; k++) {
                int ni = i + dy[k];
                int nj = j + dx[k];
                if (ni < 0 || nj < 0 || h <= ni || w <= nj || pixel[ni][nj] == '.') continue;
                ds.unite(i*w+j, ni*w+nj);
            }
            return true;
        }
        return false;
    }

    class DisjointSet {
        int[] data;

        public DisjointSet(int n){
            data = new int[n];
            for (int i=0; i<n; i++) data[i] = i;
        }

        public int find(int x){
            if(data[x] == x) return x;
            return data[x] = find(data[x]);
        }

        public boolean same(int x,int y){
            return find(x) == find(y);
        }

        public void unite(int x,int y){
            if (find(x) == find(y)) return;
            data[find(x)] = find(y);
        }

        public String toString() {
            return Arrays.toString(data);
        }
    }
}

感想

バグらせることもなく、さくっと解けていい感じ。

同じような問題をどこかでやったような気がするけど忘れた。