Famous problems

Problems include, Rat in a maze. Showing shortest path. These programs should give a very good idea on how I do my recursion
ShivanshJ · Mar 24, 2017 · 82057b2 · 82057b2
1 parent 53741e2
commit 82057b2
Show file tree

Hide file tree

Showing 5 changed files with 491 additions and 0 deletions.
diff --git a/Maze Shortest cost path_Dynamic(Top-down).cpp b/Maze Shortest cost path_Dynamic(Top-down).cpp
@@ -0,0 +1,82 @@
+#include <stdio.h>
+#include <math.h>
+#include <stdlib.h>
+#include<iostream>
+using namespace std;
+
+#include <limits.h> //For using INT_MAX
+#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)
+
+/*
+Note: In top-down dynamic,
+I noticed that the recursions are usually combined with addition operator ( + ),
+In this case, since the shortest path is being found, we use the function min() on the three recursions
+
+LOOK AT the other commented approach IN THE NAIVE.cpp file for this code
+*/
+
+int save[10][10]={0}; //2D Matrix constructed for saving purposes
+
+int min(int x, int y, int z)
+{
+   if (x < y)
+      return (x < z)? x : z;
+   else
+      return (y < z)? y : z;
+}
+
+int fx(int m , int n , int **ar, int cost)
+{ 
+
+	 if (n < 0 || m < 0 || ar[m][n]==0)  //IF WALL CONDITION NOT THERE, REMOVE AR[M][N]==0 part
+      return INT_MAX;
+
+    if(save[m][n]>0)
+    	return save[m][n];
+
+	if(m==0 && n==0)
+	{	
+
+		return ar[m][n];
+	}
+	else 
+	{
+		save[m][n]= ar[m][n] + min( fx(m-1,n,ar,cost+ ar[m][n]) , fx(m,n-1,ar,cost+ ar[m][n]) , fx(m-1,n-1,ar, cost+ ar[m][n]) );	
+	}
+	return save[m][n];
+}
+
+int main()
+{ int m,n;
+ cout<<"Enter row and column: \n";
+ cin>>m>>n;
+
+//Dynamic initialization of 2d array
+	int **ar=(int **)malloc(m*sizeof(int *));
+	F(i,0,n)
+	{
+		ar[i]= (int *)malloc(m*n*sizeof(int));
+	}
+//Taking input
+	cout<<"Enter cost of each point in matrix and walls as 0\n";
+	F(i,0,m)
+	{ F(j,0,n)
+		cin>>ar[i][j];
+
+	}
+//Printing the matrix	
+	cout<<endl<<"Matrix is: \n";
+	F(i,0,m)
+	{ F(j,0,n)
+		{
+		cout<<ar[i][j]<<"  ";}
+		cout<<endl;
+	}
+cout<<endl;
+//Final result
+	cout<<"Minimum Cost is: ";
+	cout<<fx(m-1,n-1,ar, 0);
+
+
+return 0;
+}
diff --git a/Maze Shortest cost path_Memoized.cpp b/Maze Shortest cost path_Memoized.cpp
@@ -0,0 +1,93 @@
+#include <stdio.h>
+#include <math.h>
+#include <stdlib.h>
+#include<iostream>
+using namespace std;
+
+#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)
+
+
+int mina(int a , int b)
+{ 
+return a<b?a:b;
+
+}
+
+void  fx(int m , int n , int **ar)
+{
+
+	int cost[m][n];
+	cost[0][0]=ar[0][0];
+
+	F(j,1,n)
+	 {
+
+	 	cost[0][j]=cost[0][j-1] + ar[0][j];
+
+	 }
+
+	 F(j,1,m)
+	 {
+
+	 	cost[j][0]=cost[j-1][0] + ar[j][0];
+
+	 }
+
+	F(i,1,m)
+	{ F(j,1,n)
+		{   
+
+
+			cost[i][j]= mina(cost[i-1][j] , cost[i][j-1]) + ar[i][j];
+		}
+	}
+
+
+	cout<<cost[m-1][n-1];
+}
+
+int main()
+{ int m,n;
+ cout<<"Enter row and column: \n";
+ cin>>m>>n;
+
+
+	int **ar=(int **)malloc(m*sizeof(int *));
+	F(i,0,n)
+	{
+		ar[i]= (int *)malloc(m*n*sizeof(int));
+	}
+
+	cout<<"Enter cost of each point in matrix\n";
+	F(i,0,m)
+	{ F(j,0,n)
+		cin>>ar[i][j];
+
+	}
+
+	/*int ch=1;
+	while(ch)
+	{int x,y;
+	cout<<"Enter position  position: \n";
+	cin>>x>>y;
+	cout<<"Want more walls? 1 for yes, 0 for no  :   ";
+	cin>>ch;
+	ar[x][y]=0;
+	}*/
+
+
+	cout<<endl<<"Matrix is: \n";
+	F(i,0,m)
+	{ F(j,0,n)
+		{
+		cout<<ar[i][j]<<"  ";}
+		cout<<endl;
+	}
+cout<<endl;
+
+
+	cout<<"Minimum Cost is: ";
+	fx(m,n,ar);
+
+return 0;
+}
diff --git a/Maze Shortest cost path_Naive.cpp b/Maze Shortest cost path_Naive.cpp
@@ -0,0 +1,91 @@
+#include <stdio.h>
+#include <math.h>
+#include <stdlib.h>
+#include<iostream>
+using namespace std;
+
+#include <limits.h> //For using INT_MAX
+#define F(i,a,b) for(int i= (int)(a) ; i < (int)(b) ; i++)
+
+int best=INT_MAX;
+void fx(int m , int n , int **ar, int cost)
+{ 
+	//Return condition
+	 if (n < 0 || m < 0 || ar[m][n]==0)  //IF WALL CONDITION NOT THERE, REMOVE AR[M][N]==0 part
+      return;
+    //Accept condition
+	if(m==0 && n==0)
+	{	cost+=ar[m][n];
+		if(cost<best)
+			best=cost;
+		return;
+	}
+	//Recursive function
+	else 
+	{
+		fx(m-1,n,ar,cost+ ar[m][n]); 
+		fx(m,n-1,ar,cost+ ar[m][n]); 
+		fx(m-1,n-1,ar, cost+ ar[m][n]);	
+	}
+	return;
+}
+
+int main()
+{ int m,n;
+ cout<<"Enter row and column: \n";
+ cin>>m>>n;
+
+//Dynamic initialization of 2d array
+	int **ar=(int **)malloc(m*sizeof(int *));
+	F(i,0,n)
+	{
+		ar[i]= (int *)malloc(m*n*sizeof(int));
+	}
+//Taking input
+	cout<<"Enter cost of each point in matrix and walls as 0\n";
+	F(i,0,m)
+	{ F(j,0,n)
+		cin>>ar[i][j];
+
+	}
+//Printing the matrix	
+	cout<<endl<<"Matrix is: \n";
+	F(i,0,m)
+	{ F(j,0,n)
+		{
+		cout<<ar[i][j]<<"  ";}
+		cout<<endl;
+	}
+cout<<endl;
+//Final result
+	cout<<"Minimum Cost is: ";
+	fx(m-1,n-1,ar, 0);
+	cout<<endl<<best;
+
+return 0;
+}
+/* Another approach for recursion, this doesn't need: global variable best, 'int cost' in void fx(.. , .. , .. )
+
+int min(int x, int y, int z)
+{ if (x < y)
+      return (x < z)? x : z;
+   else
+      return (y < z)? y : z;
+}
+
+void fx(int m , int n , int **ar)
+{ 
+	 if (n < 0 || m < 0 || ar[m][n]==0)  //IF WALL CONDITION NOT THERE, REMOVE AR[M][N]==0 part
+      return;
+      
+	if(m==0 && n==0)
+		return ar[m][n];
+	else 
+	{	return ar[m][n] + min ( fx(m-1,n,ar), 
+		fx(m,n-1,ar),
+		fx(m-1,n-1,ar );	
+	}
+	return;
+}
+
+*/
diff --git a/Maze show all paths.cpp b/Maze show all paths.cpp
@@ -0,0 +1,96 @@
+#include<stdio.h>
+#define M 3
+#define N 3
+#include<iostream>
+#include<stdlib.h>
+using namespace std;
+
+
+int a[M][N]={ {1, 2, 3}, {4, 5, 6} , {7,8,9}};
+
+int count=0;
+int *b=(int *)malloc(M*N*sizeof(int)+1);
+
+
+
+
+void fx(int i1,int j1,int b[7],int k)
+{
+	int i,j,l;
+
+	if(i1>M-1 || j1>N-1)
+		return;
+
+
+	b[k]=a[i1][j1];
+
+	if(i1==M-1 && j1==N-1)
+	{
+		for(l=0;l<=k;l++)
+		{
+			printf("%d ",b[l]);
+		}
+		printf("\n");
+		count++;
+		return;
+	}
+
+	fx(i1+1,j1,b,k+1);
+	fx(i1,j1+1,b,k+1);
+
+
+}
+int main(){
+	int x;
+	for(x=0; x<(M*N+1); x++)
+ 		b[x]=0;
+
+	fx(0,0,b,0);
+	printf("Count is: %d",count);
+	return 0;
+}
+
+/* MEMOIZED VERSION FROM geeksforgeeks, LOOK AT HOW FIRST ROW AND COLUMN ARE INITIALIZED
+http://www.geeksforgeeks.org/count-possible-paths-top-left-bottom-right-nxm-matrix/
+
+
+#include <iostream>
+using namespace std;
+
+// Returns count of possible paths to reach cell at row number m and column
+// number n from the topmost leftmost cell (cell at 1, 1)
+int numberOfPaths(int m, int n)
+{
+    // Create a 2D table to store results of subproblems
+    int count[m][n];
+
+    // Count of paths to reach any cell in first column is 1
+    for (int i = 0; i < m; i++)
+        count[i][0] = 1;
+
+    // Count of paths to reach any cell in first column is 1
+    for (int j = 0; j < n; j++)
+        count[0][j] = 1;
+
+    // Calculate count of paths for other cells in bottom-up manner using
+    // the recursive solution
+    for (int i = 1; i < m; i++)
+    {
+        for (int j = 1; j < n; j++)
+
+            // By uncommenting the last part the code calculatest he total
+            // possible paths if the diagonal Movements are allowed
+            count[i][j] = count[i-1][j] + count[i][j-1]; //+ count[i-1][j-1];
+
+    }
+    return count[m-1][n-1];
+}
+
+// Driver program to test above functions
+int main()
+{
+    cout << numberOfPaths(3, 3);
+    return 0;
+}
+
+*/