Given a binary square matrix of characters having size N x N such that 1 represents land and 0 represents water, the task is to find the longest straight-line path a person can travel on land without falling into water or outside for each cell (i, j). The straight line can be either horizontal, vertical, or diagonal.
Examples:
Input: N = 4, matrix[][] = { {0, 1, 0, 1}, {0, 1, 1, 1}, {1, 0, 1, 1}, {0, 0, 0, 0} }
Output: 3
Explanation: For each index (i, j), the below output matrix shows the length of the maximum path having continuous land that a person can travel in a straight line.
0 3 0 3
0 3 3 3
2 0 2 3
0 0 0 0
Therefore, the longest straight-line path is 3.Input: N = 3, matrix[][] = { {0, 1, 1}, {0, 0, 0}, {1, 1, 1} }
Output: 3
Explanation: For each index (i, j), the below output matrix shows the length of the maximum path having continuous land that a person can travel in a straight line.
0 2 2
0 0 0
3 3 3
Therefore, the longest straight-line path is 3.
Approach: Implement the idea below to solve the problem:
For the maximum path write the algorithms for vertical, horizontal, and diagonal traversals, and for each index (i, j) traverse over the input matrix and print the maximum length among all the functions for the same index.
Steps were taken to solve the problem:
- Write the functions for traversing in each direction, Formally vertical(), horizontal(), and diagonal().
- Run these functions for each index (i, j) of the input matrix.
- Output the maximum path by comparing the length of all possible paths for each index (i, j).
Below is the code to implement the above approach:
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// Input value of Nconst int N = 3;// Input matrixchar ch[N][N] = { { '0', '1', '1' }, { '0', '0', '0' }, { '1', '1', '1' } };// Declaration of Matrices for storing// length of the path in each direction// for each index of the input matrixint H[N][N], V[N][N], DB[N][N], DF[N][N], sol[N][N];// Method for traversing in// horizontal directionvoid horizontal(){ // Loop for traversing // horizontally for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Condition when '1' // is found if (ch[i][j] == '1') { // Initialized variables // to count the length int k = j, count = 0; // While continuous '1' // is found while (k < N) { if (ch[i][k] == '1') { count++; k++; } else { break; } } k--; for (int l = j; l <= k; l++) H[i][l] = count; j = k; } else { H[i][j] = 0; } } }}// Method for vertical traversalvoid vertical(){ // Loop for traversing vertically for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Condition when '1' // is found if (ch[j][i] == '1') { // Initialized variables // for count length of // continuous '1' int k = j, count = 0; // Loop while continuous // '1' is found while (k < N) { if (ch[k][i] == '1') { count++; k++; } else { break; } } k--; // Initializing length // in matrix for (int l = j; l <= k; l++) V[l][i] = count; j = k; } else { V[j][i] = 0; } } }}// Loop for traversing diagonally// in backward directionvoid diagonalBackward(){ // Loop for traversing in backward // direction diagonally for (int i = 0; i < N; i++) { int l = -1; for (int j = i; j < N; j++) { l++; // Condition when continuous // '1' is found if (ch[l][j] == '1') { // Initialized variables // to count length of // continuous '1' int m = l, n = j, count = 0; // While loop till // continuous '1' is found while (n < N) { if (ch[m][n] == '1') { count++; m++; n++; } else { break; } } m--; n--; // Initializing // values in matrix for (int p = j; p <= n; p++) { DB[l][p] = count; l++; } l--; j = n; } else { DB[l][j] = 0; } } } // Loop for traversing for (int i = 1; i < N; i++) { int l = i - 1; for (int j = 0; j < (N - i); j++) { l++; // Condition when continuous // '1' is found if (ch[l][j] == '1') { // Variables for // counting length of // continuous '1' int m = l, n = j, count = 0; // While loop for // finding length of // continuous '1' while (n < (N - i)) { if (ch[m][n] == '1') { count++; m++; n++; } else { break; } } m--; n--; // Initializing length // in matrix for (int p = j; p <= n; p++) { DB[l][p] = count; l++; } l--; j = n; } else { DB[l][j] = 0; } } }}// Loop for traversing diagonally in// forward directionvoid diagonalForward(){ // Loop for traversal for (int i = 0; i < N; i++) { int l = i; for (int j = 0; j <= i; j++) { // Condition when '1' // is found if (ch[j][l] == '1') { // Variables initialized // to count length of // continuous '1' int m = j, n = l, count = 0; // While loop for // finding the length of // continuous '1' while (m <= i) { if (ch[m][n] == '1') { count++; m++; n--; } else { break; } } m--; n++; // initializing values // in matrix for (int p = j; p <= m; p++) { DF[p][l] = count; l--; } j = m; l = n; l--; } else { DF[j][l] = 0; l--; } } } // Loop for traversal for (int i = 1; i < N; i++) { int l = i; for (int j = N - 1; j >= i; j--) { // Condition when // continuous '1' is found if (ch[l][j] == '1') { // Variables initialized int m = l, n = j, count = 0; // While loop for // counting length of // continuous '1' while (n >= i) { if (ch[m][n] == '1') { count++; m++; n--; } else { break; } } n++; m--; // Initializing values // in matrix for (int p = l; p <= m; p++) { DF[p][j] = count; j--; } l = m + 1; j = n; } else { DF[l][j] = 0; l++; } } }}// Method for creating a matrix of// maximum length for each indexvoid maxSol(){ // Solution matrix memset(sol, 0, sizeof sol); int max_ = INT_MIN; // loop for traversing for (int i = 0; i < N; i++) { // Loop for initializing // solution matrix by finding // maximum length for each index // in each direction for (int j = 0; j < N; j++) { if (H[i][j] >= V[i][j] && H[i][j] >= DB[i][j] && H[i][j] >= DF[i][j]) sol[i][j] = H[i][j]; else if (V[i][j] >= H[i][j] && V[i][j] >= DB[i][j] && V[i][j] >= DF[i][j]) sol[i][j] = V[i][j]; else if (DB[i][j] >= H[i][j] && DB[i][j] >= V[i][j] && DB[i][j] >= DF[i][j]) sol[i][j] = DB[i][j]; else sol[i][j] = DF[i][j]; max_ = max(max_, sol[i][j]); } } // Printing maximum length path cout << max_ << endl;}// Function which is called in the// driver functionvoid solution(){ // Initialization of matrices for // storing the longest path in // each index for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { H[i][j] = 0; V[i][j] = 0; DB[i][j] = 0; DF[i][j] = 0; } } // Function call for horizontal // traversals horizontal(); // Function call for vertical // traversals vertical(); // Function call for diagonal // traversals diagonalBackward(); diagonalForward(); // Function for printing matrix // of the longest path for each index // of the input matrix maxSol();}// Driver Codeint main(){ // Function call solution(); return 0;}// This Code is Contributed by Prasad Kandekar(prasad264) |
Java
// Java code to implement the approachimport java.io.*;import java.lang.*;import java.util.*;class GFG { // Input value of N static int N = 3; // Input matrix static char[][] ch = { { '0', '1', '1' }, { '0', '0', '0' }, { '1', '1', '1' } }; // Declaration of Matrices for storing // length of the path in each direction // for each index of the input matrix static int[][] H, V, DB, DF, sol; public static void main(String[] args) throws java.lang.Exception { // Function call solution(); } // Function which is called in the // driver function private static void solution() { // Initialization of matrices for // storing the longest path in // each index H = new int[N][N]; V = new int[N][N]; DB = new int[N][N]; DF = new int[N][N]; // Function call for horizontal // traversals horizontal(); // Function call for vertical // traversals vertical(); // Function call for diagonal // traversals diagonalBackward(); diagonalForward(); // Function for printing matrix // of the longest path for each index // of the input matrix maxSol(); } // Method for traversing in // horizontal direction private static void horizontal() { // Loop for traversing // horizontally for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Condition when '1' // is found if (ch[i][j] == '1') { // Initialized variables // to count the length int k = j, count = 0; // While continuous '1' // is found while (k < N) { if (ch[i][k] == '1') { count++; k++; } else { break; } } k--; for (int l = j; l <= k; l++) H[i][l] = count; j = k; } else { H[i][j] = 0; } } } } // Method for vertical traversal private static void vertical() { // Loop for traversing vertically for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Condition when '1' // is found if (ch[j][i] == '1') { // Initialized variables // for count length of // continuous '1' int k = j, count = 0; // Loop while continuous // '1' is found while (k < N) { if (ch[k][i] == '1') { count++; k++; } else { break; } } k--; // Initializing length // in matrix for (int l = j; l <= k; l++) V[l][i] = count; j = k; } else { V[j][i] = 0; } } } } // Loop for traversing diagonally // in backward direction private static void diagonalBackward() { // Loop for traversing in backward // direction diagonally for (int i = 0; i < N; i++) { int l = -1; for (int j = i; j < N; j++) { l++; // Condition when continuous // '1' is found if (ch[l][j] == '1') { // Initialized variables // to count length of // continuous '1' int m = l, n = j, count = 0; // While loop till // continuous '1' is found while (n < N) { if (ch[m][n] == '1') { count++; m++; n++; } else { break; } } m--; n--; // Initializing // values in matrix for (int p = j; p <= n; p++) { DB[l][p] = count; l++; } l--; j = n; } else { DB[l][j] = 0; } } } // Loop for traversing for (int i = 1; i < N; i++) { int l = i - 1; for (int j = 0; j < (N - i); j++) { l++; // Condition when continuous // '1' is found if (ch[l][j] == '1') { // Variables for // counting length of // continuous '1' int m = l, n = j, count = 0; // While loop for // finding length of // continuous '1' while (n < (N - i)) { if (ch[m][n] == '1') { count++; m++; n++; } else { break; } } m--; n--; // Initializing length // in matrix for (int p = j; p <= n; p++) { DB[l][p] = count; l++; } l--; j = n; } else { DB[l][j] = 0; } } } } // Loop for traversing diagonally in // forward direction private static void diagonalForward() { // Loop for traversal for (int i = 0; i < N; i++) { int l = i; for (int j = 0; j <= i; j++) { // Condition when '1' // is found if (ch[j][l] == '1') { // Variables initialized // to count length of // continuous '1' int m = j, n = l, count = 0; // While loop for // finding the length of // continuous '1' while (m <= i) { if (ch[m][n] == '1') { count++; m++; n--; } else { break; } } m--; n++; // initializing values // in matrix for (int p = j; p <= m; p++) { DF[p][l] = count; l--; } j = m; l = n; l--; } else { DF[j][l] = 0; l--; } } } // Loop for traversal for (int i = 1; i < N; i++) { int l = i; for (int j = N - 1; j >= i; j--) { // Condition when // continuous '1' is found if (ch[l][j] == '1') { // Variables initialized int m = l, n = j, count = 0; // While loop for // counting length of // continuous '1' while (n >= i) { if (ch[m][n] == '1') { count++; m++; n--; } else { break; } } n++; m--; // Initializing values // in matrix for (int p = l; p <= m; p++) { DF[p][j] = count; j--; } l = m + 1; j = n; } else { DF[l][j] = 0; l++; } } } } // Method for creating a matrix of // maximum length for each index private static void maxSol() { // Solution matrix sol = new int[N][N]; long max = Long.MIN_VALUE; // loop for traversing for (int i = 0; i < N; i++) { // Creating a StringBuilder // for output StringBuilder str = new StringBuilder(""); // Loop for initializing // solution matrix by finding // maximum length for each index // in each direction for (int j = 0; j < N; j++) { if (H[i][j] >= V[i][j] && H[i][j] >= DB[i][j] && H[i][j] >= DF[i][j]) sol[i][j] = H[i][j]; else if (V[i][j] >= H[i][j] && V[i][j] >= DB[i][j] && V[i][j] >= DF[i][j]) sol[i][j] = V[i][j]; else if (DB[i][j] >= H[i][j] && DB[i][j] >= V[i][j] && DB[i][j] >= DF[i][j]) sol[i][j] = DB[i][j]; else sol[i][j] = DF[i][j]; max = sol[i][j] > max ? sol[i][j] : max; str.append(sol[i][j]); str.append(" "); } } // Printing maximum length path System.out.println(max); }} |
Python3
# Python code to implement the approach# Input value of NN = 3# Input matrixch = [ ['0', '1', '1'], ['0', '0', '0'], ['1', '1', '1'] ]# Declaration of Matrices for storing# length of the path in each direction# for each index of the input matrixH = [[0 for i in range(N)] for j in range(N)]V = [[0 for i in range(N)] for j in range(N)]DB = [[0 for i in range(N)] for j in range(N)]DF = [[0 for i in range(N)] for j in range(N)]sol = [[0 for i in range(N)] for j in range(N)]# Method for traversing in# horizontal directiondef horizontal(): # Loop for traversing # horizontally for i in range(N): for j in range(N): # Condition when '1' # is found if ch[i][j] == '1': # Initialized variables # to count the length k, count = j, 0 # While continuous '1' # is found while k < N and ch[i][k] == '1': count += 1 k += 1 k -= 1 for l in range(j, k+1): H[i][l] = count j = k else: H[i][j] = 0# Method for vertical traversaldef vertical(): # Loop for traversing vertically for i in range(N): for j in range(N): # Condition when '1' # is found if ch[j][i] == '1': # Initialized variables # for count length of # continuous '1' k, count = j, 0 # Loop while continuous # '1' is found while k < N and ch[k][i] == '1': count += 1 k += 1 k -= 1 # Initializing length # in matrix for l in range(j, k+1): V[l][i] = count j = k else: V[j][i] = 0# Loop for traversing diagonally# in backward directiondef diagonalBackward(): # Loop for traversing in backward # direction diagonally for i in range(N): l = -1 for j in range(i, N): l += 1 # Condition when continuous # '1' is found if ch[l][j] == '1': # Initialized variables # to count length of # continuous '1' m, n, count = l, j, 0 # While loop till # continuous '1' is found while n < N and ch[m][n] == '1': count += 1 m += 1 n += 1 m -= 1 n -= 1 # Initializing # values in matrix for p in range(j, n+1): DB[l][p] = count l += 1 l -= 1 j = n else: DB[l][j] = 0 # Loop for traversing for i in range(1, N): l = i - 1 for j in range(N - i): l += 1 # Condition when continuous # '1' is found if ch[l][j] == '1': # Variables for # counting length of # continuous '1' m, n, count = l, j, 0 # While loop for # finding length of # continuous '1' while n < N - i and ch[m][n] == '1': count += 1 m += 1 n += 1 m -= 1 n -= 1 # Initializing length # in matrix for p in range(j, n+1): DB[l][p] = count l += 1 l -= 1 j = n else: DB[l][j] = 0# Loop for traversing diagonally in# forward directiondef diagonalForward(): # Loop for traversal for i in range(N): l = i for j in range(i+1): # Condition when '1' # is found if ch[j][l] == '1': # Variables initialized # to count length of # continuous '1' m, n, count = j, l, 0 # While loop for # finding the length of # continuous '1' while m <= i and n >= 0 and ch[m][n] == '1': count += 1 m += 1 n -= 1 m -= 1 n += 1 # initializing values # in matrix for p in range(j, m+1): DF[p][l] = count l -= 1 j = m l = n l -= 1 else: DF[j][l] = 0 l -= 1 # Loop for traversal for i in range(1, N): l = i for j in range(N-1, i-1, -1): # Condition when # continuous '1' is found if ch[l][j] == '1': # Variables initialized m, n, count = l, j, 0 # While loop for # counting length of # continuous '1' while m <= N-1 and n >= i and ch[m][n] == '1': count += 1 m += 1 n -= 1 m -= 1 n += 1 # Initializing values # in matrix for p in range(l, m+1): DF[p][j] = count j -= 1 l = m + 1 j = n else: DF[l][j] = 0 l += 1# Method for creating a matrix of# maximum length for each indexdef maxSol(): # Solution matrix sol = [[0 for j in range(N)] for i in range(N)] max_val = float('-inf') # loop for traversing for i in range(N): # Loop for initializing # solution matrix by finding # maximum length for each index # in each direction for j in range(N): if H[i][j] >= V[i][j] and H[i][j] >= DB[i][j] and H[i][j] >= DF[i][j]: sol[i][j] = H[i][j] elif V[i][j] >= H[i][j] and V[i][j] >= DB[i][j] and V[i][j] >= DF[i][j]: sol[i][j] = V[i][j] elif DB[i][j] >= H[i][j] and DB[i][j] >= V[i][j] and DB[i][j] >= DF[i][j]: sol[i][j] = DB[i][j] else: sol[i][j] = DF[i][j] max_val = max(max_val, sol[i][j]) # Printing maximum length path print(max_val)# Function which is called in the# driver functiondef solution(): # Function call for horizontal # traversals horizontal() # Function call for vertical # traversals vertical() # Function call for diagonal # traversals diagonalBackward() diagonalForward() # Function for printing matrix # of the longest path for each index # of the input matrix maxSol()# Function callsolution()# This Code is Contributed by Prasad Kandekar(prasad264) |
C#
// C# code to implement the approachusing System;public class GFG { // Input value of N const int N = 3; // Input matrix static char[, ] ch = { { '0', '1', '1' }, { '0', '0', '0' }, { '1', '1', '1' } }; // Declaration of Matrices for storing // length of the path in each direction // for each index of the input matrix static int[, ] H = new int[N, N]; static int[, ] V = new int[N, N]; static int[, ] DB = new int[N, N]; static int[, ] DF = new int[N, N]; static int[, ] sol = new int[N, N]; // Method for traversing in // horizontal direction static void horizontal() { // Loop for traversing // horizontally for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Condition when '1' // is found if (ch[i, j] == '1') { // Initialized variables // to count the length int k = j, count = 0; // While continuous '1' // is found while (k < N) { if (ch[i, k] == '1') { count++; k++; } else { break; } } k--; for (int l = j; l <= k; l++) H[i, l] = count; j = k; } else { H[i, j] = 0; } } } } // Method for vertical traversal static void vertical() { // Loop for traversing vertically for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { // Condition when '1' // is found if (ch[j, i] == '1') { // Initialized variables // for count length of // continuous '1' int k = j, count = 0; // Loop while continuous // '1' is found while (k < N) { if (ch[k, i] == '1') { count++; k++; } else { break; } } k--; // Initializing length // in matrix for (int l = j; l <= k; l++) V[l, i] = count; j = k; } else { V[j, i] = 0; } } } } static void diagonalBackward() { // Loop for traversing in backward // direction diagonally for (int i = 0; i < N; i++) { int l = -1; for (int j = i; j < N; j++) { l++; // Condition when continuous // '1' is found if (ch[l, j] == '1') { // Initialized variables // to count length of // continuous '1' int m = l, n = j, count = 0; // While loop till // continuous '1' is found while (n < N) { if (ch[m, n] == '1') { count++; m++; n++; } else { break; } } m--; n--; // Initializing // values in matrix for (int p = j; p <= n; p++) { DB[l, p] = count; l++; } l--; j = n; } else { DB[l, j] = 0; } } } // Loop for traversing for (int i = 1; i < N; i++) { int l = i - 1; for (int j = 0; j < (N - i); j++) { l++; // Condition when continuous // '1' is found if (ch[l, j] == '1') { // Variables for counting length of // continuous '1' int m = l, n = j, count = 0; // While loop for finding length of // continuous '1' while (n < (N - i)) { if (ch[m, n] == '1') { count++; m++; n++; } else { break; } } m--; n--; // Initializing length // in matrix for (int p = j; p <= n; p++) { DB[l, p] = count; l++; } l--; j = n; } else { DB[l, j] = 0; } } } } // Loop for traversing diagonally in // forward direction static void diagonalForward() { // Loop for traversal for (int i = 0; i < N; i++) { int l = i; for (int j = 0; j <= i; j++) { // Condition when '1' // is found if (ch[j, l] == '1') { // Variables initialized // to count length of // continuous '1' int m = j, n = l, count = 0; // While loop for // finding the length of // continuous '1' while (m <= i) { if (ch[m, n] == '1') { count++; m++; n--; } else { break; } } m--; n++; // initializing values // in matrix for (int p = j; p <= m; p++) { DF[p, l] = count; l--; } j = m; l = n; l--; } else { DF[j, l] = 0; l--; } } } // Loop for traversal for (int i = 1; i < N; i++) { int l = i; for (int j = N - 1; j >= i; j--) { // Condition when // continuous '1' is found if (ch[l, j] == '1') { // Variables initialized int m = l, n = j, count = 0; // While loop for // counting length of // continuous '1' while (n >= i) { if (ch[m, n] == '1') { count++; m++; n--; } else { break; } } n++; m--; // Initializing values // in matrix for (int p = l; p <= m; p++) { DF[p, j] = count; j--; } l = m + 1; j = n; } else { DF[l, j] = 0; l++; } } } } // Method for creating a matrix of // maximum length for each index static void maxSol() { // Solution matrix Array.Clear(sol, 0, sol.Length); int max_ = int.MinValue; // loop for traversing for (int i = 0; i < N; i++) { // Loop for initializing // solution matrix by finding // maximum length for each index // in each direction for (int j = 0; j < N; j++) { if (H[i, j] >= V[i, j] && H[i, j] >= DB[i, j] && H[i, j] >= DF[i, j]) sol[i, j] = H[i, j]; else if (V[i, j] >= H[i, j] && V[i, j] >= DB[i, j] && V[i, j] >= DF[i, j]) sol[i, j] = V[i, j]; else if (DB[i, j] >= H[i, j] && DB[i, j] >= V[i, j] && DB[i, j] >= DF[i, j]) sol[i, j] = DB[i, j]; else sol[i, j] = DF[i, j]; max_ = Math.Max(max_, sol[i, j]); } } // Printing maximum length path Console.WriteLine(max_); } // Function which is called in the // driver function static void solution() { // Initialization of matrices for // storing the longest path in // each index for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { H[i, j] = 0; V[i, j] = 0; DB[i, j] = 0; DF[i, j] = 0; } } // Function call for horizontal // traversals horizontal(); // Function call for vertical // traversals vertical(); // Function call for diagonal // traversals diagonalBackward(); diagonalForward(); // Function for printing matrix // of the longest path for each index // of the input matrix maxSol(); } // Driver Code static public void Main(string[] args) { // Function call solution(); }}// This Code is Contributed by Prasad Kandekar(prasad264) |
Javascript
// Javascript code to implement the approach// Input value of Nlet N = 3;// Input matrixlet ch = [ [ '0', '1', '1' ], [ '0', '0', '0' ], [ '1', '1', '1' ] ];// Declaration of Matrices for storing// length of the path in each direction// for each index of the input matrixlet H, V, DB, DF, sol;// Method for traversing in// horizontal directionfunction horizontal(){ // Loop for traversing // horizontally for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { // Condition when '1' // is found if (ch[i][j] == '1') { // Initialized variables // to count the length let k = j, count = 0; // While continuous '1' // is found while (k < N) { if (ch[i][k] == '1') { count++; k++; } else { break; } } k--; for (let l = j; l <= k; l++) H[i][l] = count; j = k; } else { H[i][j] = 0; } } }}// Method for vertical traversalfunction vertical(){ // Loop for traversing vertically for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) { // Condition when '1' // is found if (ch[j][i] == '1') { // Initialized variables // for count length of // continuous '1' let k = j, count = 0; // Loop while continuous // '1' is found while (k < N) { if (ch[k][i] == '1') { count++; k++; } else { break; } } k--; // Initializing length // in matrix for (let l = j; l <= k; l++) V[l][i] = count; j = k; } else { V[j][i] = 0; } } }}// Loop for traversing diagonally// in backward directionfunction diagonalBackward(){ // Loop for traversing in backward // direction diagonally for (let i = 0; i < N; i++) { let l = -1; for (let j = i; j < N; j++) { l++; // Condition when continuous // '1' is found if (ch[l][j] == '1') { // Initialized variables // to count length of // continuous '1' let m = l, n = j, count = 0; // While loop till // continuous '1' is found while (n < N) { if (ch[m][n] == '1') { count++; m++; n++; } else { break; } } m--; n--; // Initializing // values in matrix for (let p = j; p <= n; p++) { DB[l][p] = count; l++; } l--; j = n; } else { DB[l][j] = 0; } } } // Loop for traversing for (let i = 1; i < N; i++) { let l = i - 1; for (let j = 0; j < (N - i); j++) { l++; // Condition when continuous // '1' is found if (ch[l][j] == '1') { // Variables for // counting length of // continuous '1' let m = l, n = j, count = 0; // While loop for // finding length of // continuous '1' while (n < (N - i)) { if (ch[m][n] == '1') { count++; m++; n++; } else { break; } } m--; n--; // Initializing length // in matrix for (let p = j; p <= n; p++) { DB[l][p] = count; l++; } l--; j = n; } else { DB[l][j] = 0; } } }}// Loop for traversing diagonally in// forward directionfunction diagonalForward(){ // Loop for traversal for (let i = 0; i < N; i++) { let l = i; for (let j = 0; j <= i; j++) { // Condition when '1' // is found if (ch[j][l] == '1') { // Variables initialized // to count length of // continuous '1' let m = j, n = l, count = 0; // While loop for // finding the length of // continuous '1' while (m <= i) { if (ch[m][n] == '1') { count++; m++; n--; } else { break; } } m--; n++; // initializing values // in matrix for (let p = j; p <= m; p++) { DF[p][l] = count; l--; } j = m; l = n; l--; } else { DF[j][l] = 0; l--; } } } // Loop for traversal for (let i = 1; i < N; i++) { let l = i; for (let j = N - 1; j >= i; j--) { // Condition when // continuous '1' is found if (ch[l][j] == '1') { // Variables initialized let m = l, n = j, count = 0; // While loop for // counting length of // continuous '1' while (n >= i) { if (ch[m][n] == '1') { count++; m++; n--; } else { break; } } n++; m--; // Initializing values // in matrix for (let p = l; p <= m; p++) { DF[p][j] = count; j--; } l = m + 1; j = n; } else { DF[l][j] = 0; l++; } } }}// Method for creating a matrix of// maximum length for each indexfunction maxSol(){ // Solution matrix sol = new Array(N); for(let i=0; i<N; i++) sol[i]=new Array(N).fill(0); let max = Number.MIN_SAFE_INTEGER; // loop for traversing for (let i = 0; i < N; i++) { // Creating a StringBuilder // for output let str = ""; // Loop for initializing // solution matrix by finding // maximum length for each index // in each direction for (let j = 0; j < N; j++) { if (H[i][j] >= V[i][j] && H[i][j] >= DB[i][j] && H[i][j] >= DF[i][j]) sol[i][j] = H[i][j]; else if (V[i][j] >= H[i][j] && V[i][j] >= DB[i][j] && V[i][j] >= DF[i][j]) sol[i][j] = V[i][j]; else if (DB[i][j] >= H[i][j] && DB[i][j] >= V[i][j] && DB[i][j] >= DF[i][j]) sol[i][j] = DB[i][j]; else sol[i][j] = DF[i][j]; max = sol[i][j] > max ? sol[i][j] : max; str+=sol[i][j]; str+" "; } } // Printing maximum length path console.log(max);}// Function which is called in the // driver functionfunction solution(){ // Initialization of matrices for // storing the longest path in // each index H = new Array(N); for(let i=0; i<N; i++) H[i]=new Array(N).fill(0); V = new Array(N); for(let i=0; i<N; i++) V[i]=new Array(N).fill(0); DB = new Array(N); for(let i=0; i<N; i++) DB[i]=new Array(N).fill(0); DF = new Array(N); for(let i=0; i<N; i++) DF[i]=new Array(N).fill(0); // Function call for horizontal // traversals horizontal(); // Function call for vertical // traversals vertical(); // Function call for diagonal // traversals diagonalBackward(); diagonalForward(); // Function for printing matrix // of the longest path for each index // of the input matrix maxSol();}// Function callsolution(); |
Output
3
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
