fork download 
  1. #include <iostream>
  2. #include <string>
  3. #include <utility>
  4. #include <vector>
  5.  
  6. struct position {
  7. 	int row;
  8. 	int col;
  9. };
  10. using ogre_map = std::vector<std::string>;
  11.  
  12. ogre_map sample_maps[] = {
  13. 	{ // Example input 1
  14. 		"@@........",
  15. 		"@@O.......",
  16. 		".....O.O..",
  17. 		"..........",
  18. 		"..O.O.....",
  19. 		"..O....O.O",
  20. 		".O........",
  21. 		"..........",
  22. 		".....OO...",
  23. 		".........$"
  24. 	},
  25. 	{ // Example input 2
  26. 		"@@........",
  27. 		"@@O.......",
  28. 		".....O.O..",
  29. 		"..........",
  30. 		"..O.O.....",
  31. 		"..O....O.O",
  32. 		".O........",
  33. 		"..........",
  34. 		".....OO.O.",
  35. 		".........$"
  36. 	},
  37. 	{ // Challenge input 1
  38. 		"$.O...O...",
  39. 		"...O......",
  40. 		"..........",
  41. 		"O..O..O...",
  42. 		"..........",
  43. 		"O..O..O...",
  44. 		"..........",
  45. 		"......OO..",
  46. 		"O..O....@@",
  47. 		"........@@"
  48. 	},
  49. 	{ // Challenge input 2
  50. 		".@@.....O.",
  51. 		".@@.......",
  52. 		"..O..O....",
  53. 		".......O..",
  54. 		"...O......",
  55. 		"..........",
  56. 		".......O.O",
  57. 		"...O.O....",
  58. 		".......O..",
  59. 		".........$"
  60. 	}
  61. };
  62.  
  63. bool dfs(ogre_map& map, position pos) {
  64. 	char old = map[pos.row][pos.col];
  65. 	auto check_for = [&](char ch) {
  66. 		return old == ch || map[pos.row][pos.col+1] == ch ||
  67. 		       map[pos.row+1][pos.col] == ch || map[pos.row+1][pos.col+1] == ch;
  68. 	};
  69. 	if (old == '&' || check_for('O'))
  70. 	    return false; // already been there, or can't go there
  71.  
  72. 	map[pos.row][pos.col] = '&';
  73. 	if (check_for('$'))
  74. 	    return true; // we found it!
  75.  
  76. 	// recurse
  77. 	if (pos.row > 0 && dfs(map, {pos.row-1, pos.col})) // up
  78. 		return true;
  79. 	if (pos.col > 0 && dfs(map, {pos.row, pos.col-1})) // left
  80. 		return true;
  81. 	if (pos.row < map.size()-2 && dfs(map, {pos.row+1, pos.col})) // down
  82. 		return true;
  83. 	if (pos.col < map[0].size()-2 && dfs(map, {pos.row, pos.col+1})) // right
  84. 		return true;
  85.  
  86. 	// not found
  87. 	map[pos.row][pos.col] = old;
  88. 	return false;
  89. }
  90.  
  91. void biggify(ogre_map& map) {
  92. 	for (int r = map.size() - 1; r >= 0; --r)
  93. 		for (int c = map[0].size() - 1; c >= 1; --c)
  94. 			if ((r > 0 && (map[r-1][c-1] == '&' || map[r-1][c] == '&')) || map[r][c-1] == '&')
  95. 				map[r][c] = '&';
  96. }
  97.  
  98. position find_start(const ogre_map& map) {
  99. 	for (int r = 0; r < map.size(); ++r)
  100. 		for (int c = 0; c < map[0].size(); ++c)
  101. 			if (map[r][c] == '@') return {r, c};
  102. 	return {-1, -1};
  103. }
  104.  
  105. int main() {
  106. 	auto& input = sample_maps[2];
  107.  
  108. 	position ogre_start = find_start(input);
  109. 	if (ogre_start.row < 0 || ogre_start.col < 0) {
  110. 		std::cout << "Is this a joke? You didn't put an ogre anywhere on the map!\n";
  111. 		std::exit(1);
  112. 	}
  113.  
  114. 	if (dfs(input, ogre_start)) {
  115. 		biggify(input);
  116. 		for (auto& row : input) {
  117. 			std::cout << row << '\n';
  118. 		}
  119. 	} else {
  120. 		std::cout << "No Path\n";
  121. 	}
  122. 	return 0;
  123. }
Success #stdin #stdout 0s 3280KB
comments ()
stdin 
Standard input is empty
stdout 
&&O...O&&&
&&&O&&&&&&
.&&.&&&&&&
O&&O&&O.&&
.&&.&&..&&
O&&O&&O.&&
.&&&&&..&&
.&&&&&OO&&
O..O....&&
........&&
https://ideone.com/ax8TJI
language:
C++14 (gcc 8.3)
created:
9 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!