fork download
copy 
  1. #include <iostream>
  2. #include <array>
  3. #include <string>
  4. using namespace std;
  5.  
  6. #define ROW 3
  7. #define COL 3
  8.  
  9.  
  10. // Allowed = 0 
  11. // Not Allowed = 1
  12. //const int grid[ROW][COL] = {0}; 
  13.  
  14. array<array<int, ROW>, COL> grid = {{
  15. 	{0,0,0},
  16. 	{1,0,0}, 
  17. 	{0,1,0}
  18. }}; 
  19.  
  20. string to_str(const array<array<int, ROW>, COL>& g)
  21. {
  22. 	string res=""; 
  23. 	for(int i=0; i<ROW; ++i)
  24. 	{
  25. 		for(int j=0; j<COL; ++j)
  26. 		{
  27. 			res += (j==0)?"":" " + to_string(g[i][j]); 
  28. 		}
  29. 		res += "\n"; 
  30. 	}
  31. 	return res; 
  32. }
  33.  
  34.  
  35.  
  36. /**
  37.   * @brief Solving the maze requires finding only 1 path 
  38.   * @note CONSTRAINTS 
  39.   * 1) Bounds 
  40.   * 2) Allowed Cells 
  41.   * 3) Ending Condition 
  42.   */
  43. string solve_maze(const array<array<int, ROW>, COL>& g, const unsigned int r, const unsigned int c, const string& s)
  44. {
  45. 	// Ending Condition 
  46. 	if((r==(ROW-1)) && (c==(COL-1))) return s; 
  47.  
  48. 	// Only 2 steps possible: r+1 or c+1
  49. 	// Check Bounds first and allowed second 
  50. 	if( ((r+1)<ROW) && (g[r+1][c] == 0) ) {auto res = solve_maze(g, r+1, c, s + (s==""?"":",") + "D"); if(res!="") return res;} 
  51. 	if( ((c+1)<COL) && (g[r][c+1] == 0) ) {auto res = solve_maze(g, r, c+1, s + (s==""?"":",") + "R"); if(res!="") return res;} 
  52. 	return ""; 
  53. }
  54.  
  55.  
  56. /**
  57.   * @brief Decorates the actual engine 
  58.   */
  59. string solve_maze(const array<array<int, ROW>, COL>& g)
  60. {
  61. 	auto res = solve_maze(g, 0,0, ""); 
  62. 	if (res=="") return "Impossibile to solve"; 
  63. 	return res; 
  64. }
  65.  
  66. int main() {
  67. 	// your code goes here
  68. 	//cout << to_str(grid) << endl; 
  69. 	cout << solve_maze(grid) << endl; 
  70. 	return 0;
  71. }
Success #stdin #stdout 0s 4360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
R,D,R,D
https://ideone.com/QrdXyv
Solve 2D Maze moving from top left corner to bottom right corner using only right and down moves
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!