1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94

# include <iostream>
int constexpr map_x_dimension = 10;
int constexpr map_y_dimension = 10;
int constexpr map_array_length = map_x_dimension * map_y_dimension;
int constexpr max_energy = 12;
int constexpr unreachable = map_array_length;
static_assert(unreachable >= map_array_length);
char constexpr barrier = 'B';
char constexpr charger = 'C';
char constexpr path = '_';
char constexpr visited = '.';
char constexpr visited_charger = 'c';
struct map
{
#define _ (path),
#define B (barrier),
#define C (charger),
char data[map_x_dimension * map_y_dimension]
{
_ _ _ _ C B B B B B
_ B _ B _ _ B _ B _
_ B _ _ B B _ B _ _
B _ _ _ B _ _ _ _ B
_ _ B _ C _ B B C B
B _ _ B B B _ _ _ B
_ _ _ _ _ _ B B B B
B B B B B C _ _ C _
B _ _ C _ _ B _ _ _
B B _ _ B _ B B B _
};
#undef C
#undef B
#undef _
};
int shortest_path(map m, int x, int y, int tx, int ty, int energy, int distance, map& original);
int minimum(int a, int b) { return a < b? a: b; }
int minimum(int a, int b, int c) { return minimum(a, minimum(b, c)); }
int minimum(int a, int b, int c, int d) { return minimum(a, minimum(b, c, d)); }
int minimum(int a, int b, int c, int d, int e) { return minimum(a, minimum(b, c, d, e)); }
int main()
{
map m;
map original = m;
int path_length = shortest_path(m, 0, 0, map_x_dimension  1, map_y_dimension  1, max_energy, 0, original);
if (path_length == unreachable) std::cout << "no solution\n";
else std::cout << path_length << " tiles traversed\n";
}
int shortest_path(map m, int x, int y, int tx, int ty, int const energy, int distance, map& original)
{
char& current = m.data[x + y * map_x_dimension];
if (x == tx && y == ty) return distance;
if (current == visited) return unreachable;
if (current == barrier) return unreachable;
bool const is_charger = (current == charger);
if (distance == energy && ! is_charger) return unreachable;
current = visited;
bool const has_left_neighbor = x > 0;
bool const has_right_neighbor = x < map_x_dimension  1;
bool const has_upper_neighbor = y > 0;
bool const has_lower_neighbor = y < map_y_dimension  1;
int search_from_charger = unreachable;
int search_left = unreachable;
int search_right = unreachable;
int search_upper = unreachable;
int search_lower = unreachable;
if (is_charger)
{
original.data[x + y * map_x_dimension] = visited_charger;
search_from_charger = shortest_path(original, x, y, tx, ty, max_energy + distance, distance, original);
}
if (has_left_neighbor) search_left = shortest_path(m, x  1, y, tx, ty, energy, distance + 1, original);
if (has_right_neighbor) search_right = shortest_path(m, x + 1, y, tx, ty, energy, distance + 1, original);
if (has_upper_neighbor) search_upper = shortest_path(m, x, y  1, tx, ty, energy, distance + 1, original);
if (has_lower_neighbor) search_lower = shortest_path(m, x, y + 1, tx, ty, energy, distance + 1, original);
return minimum(search_from_charger, search_left, search_right, search_upper, search_lower);
}
 