fork download
copy 
  1. // C++ implementation of the approach 
  2. #include <bits/stdc++.h> 
  3. using namespace std; 
  4. #define R 4 
  5. #define C 4 
  6.  
  7. // Function to return the count of possible paths 
  8. // in a maze[R][C] from (0, 0) to (R-1, C-1) that 
  9. // do not pass through any of the marked cells 
  10. int countPaths(int maze[][C]) 
  11. { 
  12. 	// If the initial cell is blocked, there is no 
  13. 	// way of moving anywhere 
  14. 	if (maze[0][0] == -1) 
  15. 		return 0; 
  16.  
  17. 	// Initializing the leftmost column 
  18. 	for (int i = 0; i < R; i++) { 
  19. 		if (maze[i][0] == 0) 
  20. 			maze[i][0] = 1; 
  21.  
  22. 		// If we encounter a blocked cell in leftmost 
  23. 		// row, there is no way of visiting any cell 
  24. 		// directly below it. 
  25. 		else
  26. 			break; 
  27. 	} 
  28.  
  29. 	// Similarly initialize the topmost row 
  30. 	for (int i = 1; i < C; i++) { 
  31. 		if (maze[0][i] == 0) 
  32. 			maze[0][i] = 1; 
  33.  
  34. 		// If we encounter a blocked cell in bottommost 
  35. 		// row, there is no way of visiting any cell 
  36. 		// directly below it. 
  37. 		else
  38. 			break; 
  39. 	} 
  40.  
  41. 	// The only difference is that if a cell is -1, 
  42. 	// simply ignore it else recursively compute 
  43. 	// count value maze[i][j] 
  44. 	for (int i = 1; i < R; i++) { 
  45. 		for (int j = 1; j < C; j++) { 
  46. 			// If blockage is found, ignore this cell 
  47. 			if (maze[i][j] == -1) 
  48. 				continue; 
  49.  
  50. 			// If we can reach maze[i][j] from maze[i-1][j] 
  51. 			// then increment count. 
  52. 			if (maze[i - 1][j] > 0) 
  53. 				maze[i][j] = (maze[i][j] + maze[i - 1][j]); 
  54.  
  55. 			// If we can reach maze[i][j] from maze[i][j-1] 
  56. 			// then increment count. 
  57. 			if (maze[i][j - 1] > 0) 
  58. 				maze[i][j] = (maze[i][j] + maze[i][j - 1]); 
  59. 		} 
  60. 	} 
  61.  
  62. 	// If the final cell is blocked, output 0, otherwise 
  63. 	// the answer 
  64. 	return (maze[R - 1][C - 1] > 0) ? maze[R - 1][C - 1] : 0; 
  65. } 
  66. // Function to return the count of all possible 
  67. // paths from (0, 0) to (n - 1, m - 1) 
  68. int numberOfPaths(int m, int n) 
  69. { 
  70. 	// We have to calculate m+n-2 C n-1 here 
  71. 	// which will be (m+n-2)! / (n-1)! (m-1)! 
  72. 	int path = 1; 
  73. 	for (int i = n; i < (m + n - 1); i++) { 
  74. 		path *= i; 
  75. 		path /= (i - n + 1); 
  76. 	} 
  77. 	return path; 
  78. } 
  79.  
  80. // Function to return the total count of paths 
  81. // from (0, 0) to (n - 1, m - 1) that pass 
  82. // through at least one of the marked cells 
  83. int solve(int maze[][C]) 
  84. { 
  85.  
  86. 	// Total count of paths - Total paths that do not 
  87. 	// pass through any of the marked cell 
  88. 	int ans = numberOfPaths(R, C) - countPaths(maze); 
  89.  
  90. 	// return answer 
  91. 	return ans; 
  92. } 
  93.  
  94. // Driver code 
  95. int main() 
  96. { 
  97. 	int maze[R][C] = { { 0, 0, 0, 0 }, 
  98. 					{ 0, -1, 0, 0 }, 
  99. 					{ -1, 0, 0, 0 }, 
  100. 					{ 0, 0, 0, 0 } }; 
  101.  
  102. 	cout << solve(maze); 
  103.  
  104. 	return 0; 
  105. } 
  106.  
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
16
https://ideone.com/v8qF3I
language:
C++ (gcc 8.3)
created:
4 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!