class MinimumCostPathUsingDFSusingRecursion {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int totalCases = s.nextInt();
for (int i = 0; i < totalCases; i++) {
int N = s.nextInt();
int data[][] = new int[N][N];
int dpStorage[][] = new int[N][N];
int sum = 0;
for (int j = 0; j < data.length; j++) {
for (int k = 0; k < data.length; k++) {
data[j][k] = s.nextInt();
sum += data[j][k];
}
}
for (int j = 0; j < data.length; j++) {
for (int k = 0; k < data.length; k++) {
dpStorage[j][k] = sum;
}
}
CalculateMinCoast(data, dpStorage, 0, 0, 0);
System.out.println(dpStorage[data.length - 1][data.length - 1]);
}
}
private static void CalculateMinCoast(int[][] data, int[][] dpStorage, int x, int y, int cost) {
if (x < 0 || y < 0 || x >= data.length || y >= data.length || dpStorage[x][y] <= cost + data[x][y]) {
return;
} else {
dpStorage[x][y] = cost + data[x][y];
int x1 = x + 1;
int y1 = y + 1;
int x2 = x - 1;
int y2 = y - 1;
int newCost = dpStorage[x][y];
CalculateMinCoast(data, dpStorage, x, y1, newCost);
CalculateMinCoast(data, dpStorage, x1, y, newCost);
CalculateMinCoast(data, dpStorage, x, y2, newCost);
CalculateMinCoast(data, dpStorage, x2, y, newCost);
}
}
}
please can anyOne tell me what is time complexity of my program … even i done memorisation (dynamic programing) in my program in my own way… but still giving TLE error.
similarly when tried to solve above problem using BFS along with memorisation in my own way, it gave me AC answer…
can anyOne tell me what are complexities of my both programs!
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
package geeksforgeeks;
import java.util.LinkedList;
import java.util.Scanner;
/**
*
* @author Hemant Dhanuka
*/
public class MinimumCostPathUsingBFSUsingLinkedListAsQueue {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int totalCases = s.nextInt();
for (int i = 0; i < totalCases; i++) {
int N = s.nextInt();
int data[][] = new int[N][N];
int dpStorage[][] = new int[N][N];
int sum = 0;
for (int j = 0; j < data.length; j++) {
for (int k = 0; k < data.length; k++) {
data[j][k] = s.nextInt();
sum += data[j][k];
}
}
for (int j = 0; j < data.length; j++) {
for (int k = 0; k < data.length; k++) {
dpStorage[j][k] = sum;
}
}
CalculateMinCoast(data, dpStorage);
System.out.println(dpStorage[data.length - 1][data.length - 1]);
}
}
private static void CalculateMinCoast(int[][] data, int[][] dpStorage) {
LinkedList<Integer> queue = new LinkedList();
queue.add(0);
queue.add(0);
queue.add(0);
int m = data.length;
while (!queue.isEmpty()) {
int x = queue.pop();
int y = queue.pop();
int cost = queue.pop();
if (x < m && y < m && x >= 0 && y >= 0) {
int newCost = cost + data[x][y];
if (dpStorage[x][y] > newCost) {
dpStorage[x][y] = newCost;
queue.add(x + 1);
queue.add(y);
// queue.add(cost+data[x+1][y]);
//was not able to add this line due to exception
queue.add(newCost);
queue.add(x - 1);
queue.add(y);
//queue.add(cost+data[x-1][y]);
queue.add(newCost);
queue.add(x);
queue.add(y + 1);
//queue.add(cost+data[x][y+1]);
queue.add(newCost);
queue.add(x);
queue.add(y - 1);
//queue.add(cost+data[x][y-1]);
queue.add(newCost);
}
}
}
}
}
