fork download
copy 
  1. /*
  2. 	author: Hitman47
  3. 	@ayusofayush
  4. 	count the number of path 
  5. */
  6.  
  7. #include<bits/stdc++.h>
  8. #define ll long long
  9. #define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  10. using namespace std;
  11.  
  12. int mat[100][100] = {{4,7,1,6},
  13. 					{5,7,3,9},
  14. 					{3,2,1,2},
  15. 					{7,1,6,3}};
  16. int dp[100][100][100];
  17. int CountPathGrid(int n,int m,int x)
  18. {
  19. 	if(x<0)
  20. 		return 0;
  21. 	if(m==0 && n==0)
  22. 	{
  23. 		if((mat[0][0] - x) ==0)
  24. 			return 1;
  25. 		else
  26. 			return 0;
  27. 	}
  28. 	if(dp[n][m][x]!=-1)
  29. 		return dp[n][m][x];
  30. 	if(n==0)
  31. 		return dp[n][m][x] = CountPathGrid(n,m-1,x-mat[n][m]);
  32. 	if(m==0)
  33. 		return dp[n][m][x] = CountPathGrid(n-1,m,x-mat[n][m]);
  34. 	return dp[n][m][x] = CountPathGrid(n,m-1,x-mat[n][m]) + 
  35. 			CountPathGrid(n-1,m,x-mat[n][m]);
  36. }
  37.  
  38. int main()
  39. {	
  40. 	int n=4,m=4,cost=25;//cin>>n>>m>>cost;
  41. 	memset(dp,-1,sizeof dp);
  42. 	cout<<CountPathGrid(n-1,m-1,cost);	
  43.  
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 19176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
https://ideone.com/LWeW05
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!