谷歌新题 - 2d灰度图

Job Hunting Interview
,
1

一个2d array， A， 可能涂黑或没涂黑，提供接口 read(x1, y1, x2, y2) 返回：

  • 1 表示全黑
  • -1 表示全白
  • 0 表示有黑有白，mix

仅通过该接口，然后调用一个写的接口 write(x1, y1, x2, y2) 在一个空白图把这个A画出来

2

补充一下，这里的(x1, y1, x2, y2)应该是 左上和右下的坐标，那么应该是如何切割细分的次数最少

3

抛砖引玉一下，这里感觉跟我以前碰到的segment tree的题目思路很像，那个是一维。也就是mix的才需要继续细分

image
image.png1770×866 144 KB

4

这个是不是会给出那个2d array的长度呀。要不要怎么知道这个图一共有多大呀？

5

input是 matrix，当然知道长度

6

这个解法可以吗？每一次都拆分为4个小块，只有黑色的部分需要画出来。

public class Solution {
    public void drawGraph(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        dfs(0, 0, row-1, col-1);
    }
    
    private void dfs(int x1, int y1, int x2, int y2) {
        if (read(x1, y1, x2, y2) == 1) {
            write(x1, y1, x2, y2);
            return;
        } else if (read(x1, y1, x2, y2) == -1) {
            return;
        }
        
        //  * |
        // --------
        //    |
        dfs(x1, y1, x2/2, y2/2);
        
        //    |  *
        // --------
        //    |
        dfs(x1, y2/2, x2/2, y2);
        
        //    |
        // --------
        //  * |
        dfs(x2/2, y1, x2, y2/2);
        
        //    |
        // --------
        //    | *
        dfs(x2/2, y2/2, x2, y2);
    }
}
7

如果是全黑或全白，直接调用write就行了，唯一要处理的是mix

8

这里除以2，要不要+1

9

不用吧。四个case应该就把原来的大图都cover了。只要保证最外面的边界不变就好了，中间做除法的地方只是会有导致四个小图的形状不一样。

10

你再确认一下哈，可以举个例子试试，另外看下x1>x2或y1>y2的情况

11

先横切再竖切这样可以吗?

queue(int x1, int y1, int x2, int y2, boolean cut)
{
	if(x1 > x2 || y1 > y2) return;
	int ans = read(x1,y1,x2,y2);
	if(ans == 1) write(x1,y1,x2,y2);
	else if(ans == 0)
	{
		if(cut)
		{
			int midx = x1 + (x2-x1)/2;
			queue(x1,y1,midx,y2,!cut);
			queue(midx+1,y1,x2,y2,!cut);
		}
		else
		{
			int midy = y1 + (y2-y1)/2;
			queue(x1,y1,x2,midy,!cut);
			queue(x1,midy+1,x2,y2,!cut);
		}
	}
}
12

目测没问题