Найдите самую длинную линию в массиве 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

Я думаю, вам нужно использовать технику возврата, потому что она пробует все возможные способы на доске, пожалуйста, прочитайте о возврате