526互联

LeetCode -- 764. 最大加号标志

发布时间 2023-07-08 09:45:37作者: zhangkang666

 利用动态规划的思想，把每个格子上下左右连续的1的个数算出来，再从头到尾遍历一遍即可获得答案。

c ++ 
class Solution {
public:
    int orderOfLargestPlusSign(int n, vector<vector<int>>& mines) {
        vector<vector<int>> up(n + 1, vector<int>(n + 1, 0));
        vector<vector<int>> dn(n + 1, vector<int>(n + 1, 0));
        vector<vector<int>> lt(n + 1, vector<int>(n + 1, 0));
        vector<vector<int>> rt(n + 1, vector<int>(n + 1, 0));

        vector<vector<int>> g(n, vector<int>(n, 1));

        for(auto it : mines) {
            g[it[0]][it[1]] = 0;
        }

        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j < n; j ++ ) {
                if(i != 0 && g[i - 1][j] == 1) up[i][j] = up[i - 1][j] + 1;
                if(j != 0 && g[i][j - 1] == 1) lt[i][j] = lt[i][j - 1] + 1;
            }
        }

        for(int i = n - 1; i >= 0; i -- ) {
            for(int j = n - 1; j >= 0; j -- ) {
                if(i != n - 1 && g[i + 1][j] == 1) dn[i][j] = dn[i + 1][j] + 1;
                if(j != n - 1 && g[i][j + 1] == 1) rt[i][j] = rt[i][j + 1] + 1;
            }
        }

        int res = 0;
        bool flag = false;
        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j < n; j ++ ) {
                if(g[i][j] == 1) {
                    flag = true;
                    res = max(res, min(up[i][j], min(dn[i][j], min(lt[i][j], rt[i][j]))));
                }
            }
        }

        if(flag) return res + 1;
        return res;
    }
};
java
class Solution {
    public int orderOfLargestPlusSign(int n, int[][] mines) {
        int[][] g = new int[n][n];
        int[][] up = new int[n][n];
        int[][] dn = new int[n][n];
        int[][] lt = new int[n][n];
        int[][] rt = new int[n][n];
        
        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j < n; j ++ ) {
                g[i][j] = 1;
            }
        }

        for(int i = 0; i < mines.length; i ++ ) {
            g[mines[i][0]][mines[i][1]] = 0;
        }

        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j < n; j ++ ) {
                if(i != 0 && g[i - 1][j] == 1) up[i][j] = up[i - 1][j] + 1;
                if(j != 0 && g[i][j - 1] == 1) lt[i][j] = lt[i][j - 1] + 1;
            }
        }

        for(int i = n - 1; i >= 0; i -- ) {
            for(int j = n - 1; j >= 0; j -- ) {
                if(i != n - 1 && g[i + 1][j] == 1) dn[i][j] = dn[i + 1][j] + 1;
                if(j != n - 1 && g[i][j + 1] == 1) rt[i][j] = rt[i][j + 1] + 1;
            }
        }

        int res = 0;
        boolean flag = false;

        for(int i = 0; i < n; i ++ ) {
            for(int j = 0; j < n; j ++ ) {
                if(g[i][j] == 1) {
                    flag = true;
                    res = Math.max(res, Math.min(up[i][j], Math.min(dn[i][j], Math.min(lt[i][j], rt[i][j]))));
                } 
            }
        }
        if(flag) return res + 1;
        return res;
    }
}
python
class Solution:
    def orderOfLargestPlusSign(self, n: int, mines: List[List[int]]) -> int:
        g = [[1] * n for _ in range(n)]
        up = [[0] * n for _ in range(n)]
        dn = [[0] * n for _ in range(n)]
        lt = [[0] * n for _ in range(n)]
        rt = [[0] * n for _ in range(n)]

        for a in mines:
            g[a[0]][a[1]] = 0
        
        for i in range(n):
            for j in range(n):
                if i != 0 and g[i - 1][j] == 1:
                    up[i][j] = up[i - 1][j] + 1
                if j != 0 and g[i][j - 1] == 1:
                    lt[i][j] = lt[i][j - 1] + 1
        
        for i in range(n - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                if i != n - 1 and g[i + 1][j] == 1:
                    dn[i][j] = dn[i + 1][j] + 1
                if j != n - 1 and g[i][j + 1] == 1:
                    rt[i][j] = rt[i][j + 1] + 1

        res = 0
        flag = False
        for i in range(n):
            for j in range(n):
                if g[i][j] == 1:
                    flag = True
                    res = max(res, min(up[i][j], dn[i][j], lt[i][j], rt[i][j]))

        if flag:
            return res + 1
        return res
js
/**
 * @param {number} n
 * @param {number[][]} mines
 * @return {number}
 */
var orderOfLargestPlusSign = function(n, mines) {
    let g = new Array(n);
    let up = new Array(n);
    let dn = new Array(n);
    let lt = new Array(n);
    let rt = new Array(n);

    for(let i = 0; i < n; i ++ ) {
        g[i] = new Array(n).fill(1);
        up[i] = new Array(n).fill(0);
        dn[i] = new Array(n).fill(0);
        lt[i] = new Array(n).fill(0);
        rt[i] = new Array(n).fill(0);
    }

    for(let i = 0; i < mines.length; i ++ ) {
        g[mines[i][0]][mines[i][1]] = 0;
    }

    for(let i = 0; i < n; i ++ ) {
        for(let j = 0; j < n; j ++ ) {
            if(i != 0 && g[i - 1][j] == 1) up[i][j] = up[i - 1][j] + 1;
            if(j != 0 && g[i][j - 1] == 1) lt[i][j] = lt[i][j - 1] + 1;
        }
    }

    for(let i = n - 1; i >= 0; i -- ) {
        for(let j = n - 1; j >= 0; j -- ) {
            if(i != n - 1 && g[i + 1][j] == 1) dn[i][j] = dn[i + 1][j] + 1;
            if(j != n - 1 && g[i][j + 1] == 1) rt[i][j] = rt[i][j + 1] + 1;
        }
    }

    let res = 0;
    let flag = false;
    for(let i = 0; i < n; i ++ ) {
        for(let j = 0; j < n; j ++ ) {
            if(g[i][j] === 1) {
                flag = true;
                res = Math.max(res, Math.min(up[i][j], Math.min(dn[i][j], Math.min(lt[i][j], rt[i][j]))));
            }
        }
    }

    if(flag) {
        return res + 1;
    }
    return res;
};
golang
func max(a int, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a int, b int) int {
    if a < b {
        return a
    }
    return b
}

func orderOfLargestPlusSign(n int, mines [][]int) int {
    g := make([][]int, n)
    up := make([][]int, n)
    dn := make([][]int, n)
    lt := make([][]int, n)
    rt := make([][]int, n)

    for i := 0; i < n; i ++ {
        g[i] = make([]int, n)
        up[i] = make([]int, n)
        dn[i] = make([]int, n)
        lt[i] = make([]int, n)
        rt[i] = make([]int, n)
    }

    for i := 0; i < n; i ++ {
        for j := 0; j < n; j ++ {
            g[i][j] = 1
        }
    }

    for i := 0; i < len(mines); i ++ {
        g[mines[i][0]][mines[i][1]] = 0;
    }

    for i := 0; i < n; i ++ {
        for j := 0; j < n; j ++ {
            if i != 0 && g[i - 1][j] == 1 {
                up[i][j] = up[i - 1][j] + 1
            }
            if j != 0 && g[i][j - 1] == 1 {
                lt[i][j] = lt[i][j - 1] + 1
            }
        }
    }

    for i := n - 1; i >= 0; i -- {
        for j := n - 1; j >= 0; j -- {
            if i != n - 1 && g[i + 1][j] == 1 {
                dn[i][j] = dn[i + 1][j] + 1
            }
            if j != n - 1 && g[i][j + 1] == 1 {
                rt[i][j] = rt[i][j + 1] + 1
            }
        }
    }

    res := 0
    flag := false
    for i := 0; i < n; i ++ {
        for j := 0;  j < n; j ++ {
            if g[i][j] == 1 {
                flag = true
                res = max(res, min(up[i][j], min(dn[i][j], min(lt[i][j], rt[i][j]))));
            }
        }
    }

    if flag {
        return res + 1
    }
    return res
}