If you write code -- do it in Java If pseudocode, explain why it is correct. Ana
ID: 3587702 • Letter: I
Question
If you write code -- do it in Java
If pseudocode, explain why it is correct.
Analyze time complexity as well.
Problem 3: (5 + 2 points) In the city, there are n street going from east to west and numbered from south to north (so, the first street is the southmost one). There are also m avenues going from south to north and numbered from east to west (so, the first avenue is the eastmost one). Design an algorithm that takes a list of dangerous crosses and computes the number of paths going always west or north from the corner of the first street and the first avenue to the corner of the n-th street and the m-th avenue such that the path does not go through dangerous crosses. The complexity of the algorithm should be O(mnExplanation / Answer
So this is a n*m matrix where n is number of rows and m is number of street .
We should start from bottom right corner to top left corner. There are dangerous cross in between them we have to find all path those don't go through these cross.
package com.test;
public class PrintPath {
public static void printAllPathsUtil(int mat[][], int i, int j, int m, int n, int path[], int pi)
{
// Reached the bottom of the matrix so we are left with
// only option to move right
if (i == 0)
{
for (int k = n-1; k >=j; k--)
path[pi + j -k ] = mat[i][k];
for (int l = 0; l < pi + n-j ; l++)
System.out.print(path[l] + " ");
System.out.println();
return;
}
// Reached the right corner of the matrix we are left with
// only the downward movement.
if (j == 0)
{
for (int k = m-1; k >=i; k--)
path[pi + k - i] = mat[k][j];
for (int l = 0; l < pi + m - i; l++)
System.out.print(path[l] + " ");
System.out.println();
return;
}
// Add the current cell to the path being generated
path[pi] = mat[i][j];
// Print all the paths that are possible after moving down
printAllPathsUtil(mat, i - 1, j, m, n, path, pi + 1);
// Print all the paths that are possible after moving right
printAllPathsUtil(mat, i, j-1, m, n, path, pi + 1);
// Print all the paths that are possible after moving diagonal
printAllPathsUtil(mat, i-1, j-1, m, n, path, pi + 1);
}
// The main function that prints all paths from top left to bottom right
// in a matrix 'mat' of size mXn
public static void printAllPaths(int mat[][], int m, int n)
{
int []path = new int[m+n];
printAllPathsUtil(mat, m-1, n-1, m, n, path, 0);
}
public static void main(String[] args) {
int[][] arr=new int[2][2];
int k=0;
for(int i=0;i<2;i++)
{
for(int j=0;j<2;j++)
{
arr[i][j] = ++k;
}
}
printAllPaths(arr, 2, 2);
}
}