java - 查找 2D (MxM) 数组(垂直、水平或对角线)中最长的线

Question

使用给定方阵 (MxM) 查找最长直线的长度。 (允许垂直、水平或对角线)(最长线的长度 = 连续 1 的数量)

即)输入:

{
{0,0,0,0,0,0,0,0},
{0,0,1,0,1,0,0,0},
{0,1,0,1,0,0,0,0},
{1,1,1,1,1,1,1,0},
{0,1,0,0,0,1,0,0},
{1,1,0,0,0,0,1,0},
{0,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0}
}

输出:7(在本例中，第 4 个水平行是最长的行。)

我的java代码:

public class LongestLine {
    private int hmax = 0;
    private int vmax = 0;
    private int rdmax = 0; // right down direction
    private int ldmax = 0; // left down direction


    public int longestLine(int[][] grid) {

        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[i].length; j++) {
                if(grid[i][j] == 1) update(grid, i, j);
            }
        }

        return Math.max(Math.max(hmax, vmax), Math.max(rdmax, ldmax));
    }

    private void update(int[][] grid, int i, int j) {
        int h = 1, v = 1, rd = 1, ld = 1;

        if(j < grid[i].length - 1 && grid[i][j+1] == 1) h = updateH(grid, i, j+1, h);
        if(i < grid.length - 1 && grid[i+1][j] == 1) v = updateV(grid, i+1, j, v);
        if(j < grid[i].length - 1 && i < grid.length - 1 && grid[i+1][j+1] == 1) 
            rd = updateRD(grid, i+1, j+1, rd);
        if(j > 0 && i < grid.length - 1 && grid[i+1][j-1] == 1) 
            ld = updateLD(grid, i+1, j-1, ld);

        hmax = Math.max(h, hmax);
        vmax = Math.max(v, vmax);
        rdmax = Math.max(rd, rdmax);
        ldmax = Math.max(ld, ldmax);
    }

    private int updateH(int[][] grid, int i, int j, int h) {
        h++;
        if(j < grid[i].length - 1 && grid[i][j+1] == 1) h = updateH(grid, i, j+1, h);
        return h;
    }

    private int updateV(int[][] grid, int i, int j, int v) {
        v++;
        if(i < grid.length - 1 && grid[i+1][j] == 1) v = updateV(grid, i+1, j, v);
        return v;
    }

    private int updateRD(int[][] grid, int i, int j, int rd) {
        rd++;
        if(j < grid[i].length - 1 && i < grid.length - 1 && grid[i+1][j+1] == 1) 
            rd = updateRD(grid, i+1, j+1, rd);
        return rd;
    }

    private int updateLD(int[][] grid, int i, int j, int ld) {
        ld++;
        if(j > 0 && i < grid.length - 1 && grid[i+1][j-1] == 1) 
            ld = updateLD(grid, i+1, j-1, ld);
        return ld;
    }
}

我的代码似乎可以工作，但我不确定这是否是最有效的代码。你觉得这样可以吗？或者有没有更快/更简单的实现？ (首选 Java 格式的答案。)

Answer 1

我认为你需要使用回溯技术，因为它会尝试董事会中所有可能的方式请阅读有关回溯的内容