首页 > 其他 > 详细

[LeetCode]Smallest Rectangle Enclosing Black Pixels

时间:2015-12-01 08:24:40      阅读:1190      评论:0      收藏:0      [点我收藏+]

用的dfs,但是感觉这个方法应该不是最优的,否则这个题目不应该是hard

public class Solution {
    int up = Integer.MAX_VALUE;
    int low = Integer.MIN_VALUE;
    int left = Integer.MAX_VALUE;
    int right = Integer.MIN_VALUE;
    public int minArea(char[][] image, int x, int y) {
        boolean[][] record = new boolean[image.length][image[0].length];
        helper(image, record, x, y);
        return (low - up + 1) * (right - left + 1);
    }
    public void helper(char[][] image, boolean [][] record, int x, int y) {
        record[x][y] = true;
        up = Math.min(up, x);
        low = Math.max(low, x);
        left = Math.min(left, y);
        right = Math.max(right, y);
        if (x > 0 && image[x - 1][y] == 1 && !record[x - 1][y]) {
            helper(image, record, x - 1, y);
        }
        if (x + 1 < image.length && image[x + 1][y] == 1 && !record[x + 1][y]) {
            helper(image, record, x + 1, y);
        }
        if (y > 0 && image[x][y - 1] == 1 && !record[x][y - 1]) {
            helper(image, record, x, y - 1);
        }
        if (y + 1 < image[0].length && image[x][y + 1] == 1 && !record[x][y + 1]) {
            helper(image, record, x, y + 1);
        }
    }
}

后来看了下网上的思路, 写了一个二分搜索的

[LeetCode]Smallest Rectangle Enclosing Black Pixels

原文:http://www.cnblogs.com/vision-love-programming/p/5009031.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!