https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=233

http://blog.csdn.net/zhanxinhang/article/details/6706217

http://zkread.com/article/1205271.html

Merge QuadTree(G)

有两个用quad tree表示的二维地图，第一个用1表示水，0表示陆地，第二个用1表示污染，0表示干净。

返回一个新的quad tree存放所有受污染的水域

注意在生成新树的时候要同时剪枝。比如一块地方全是陆地，就不用再细化下去了。

简单的递归调用merge quad tree。注意一边是灰色，一边是黑色的时候需要deepcopy灰色部分子树。

package google;

public class QuadTree {
    int val; 
    QuadTree[] children;

    public QuadTree(int val){
        this.val = val;
        children = new QuadTree[4];
    }

    public static QuadTree deepClone(QuadTree root){
        if(root==null) return null;
        QuadTree ans = new QuadTree(root.val);
        for(int i=0;i<4;i++)
            ans.children[i] = deepClone(root.children[i]);
        return ans;
    }

    public static QuadTree merge(QuadTree root1, QuadTree root2){
        if(root1==null || root2==null) return null;
        if(root1.val==0 || root2.val==0) return new QuadTree(0);
        else if(root1.val==1&&root2.val==1) return new QuadTree(1);
        else if(root1.val==1) return deepClone(root2);
        else if(root2.val==1) return deepClone(root1);
        else{
            QuadTree[] tmp = new QuadTree[4]; int count0 = 0; int count1 = 0;
            for(int i=0;i<4;i++){
                tmp[i] = merge(root1.children[i], root2.children[i]);
                if(tmp[i].val==0) count0++;
                if(tmp[i].val==1) count1++;
            }
            if(count0==4) return new QuadTree(0);
            if(count1==4) return new QuadTree(1);
            QuadTree ans = new QuadTree(2);
            ans.children = tmp;
            return ans;
        }
    }

    public static void print(QuadTree node, int level){
        System.out.println(level + " " +node.val);
        if(node.val==2){
            for(int i=0;i<4;i++)
                print(node.children[i], level+1);
        }
    }

    public static void main(String[] args){
        QuadTree root1 = new QuadTree(2); 
        root1.children[0] = new QuadTree(1);root1.children[1] = new QuadTree(2);
        root1.children[2] = new QuadTree(2);root1.children[3] = new QuadTree(0);
        root1.children[1].children[0] = new QuadTree(0); root1.children[1].children[1] = new QuadTree(0);
        root1.children[1].children[2] = new QuadTree(0); root1.children[1].children[3] = new QuadTree(1);

        root1.children[2].children[0] = new QuadTree(0); root1.children[2].children[1] = new QuadTree(0);
        root1.children[2].children[2] = new QuadTree(0); root1.children[2].children[3] = new QuadTree(1);

        QuadTree root2 = new QuadTree(2); 
        root2.children[0] = new QuadTree(0);root2.children[1] = new QuadTree(2);
        root2.children[2] = new QuadTree(1);root2.children[3] = new QuadTree(1);

        root2.children[1].children[0] = new QuadTree(1);root2.children[1].children[1] = new QuadTree(0);
        root2.children[1].children[2] = new QuadTree(0);root2.children[1].children[3] = new QuadTree(0);

        QuadTree ans = merge(root1, root2);
        print(ans,0);

    }


}