Please help me (Shortest path - recursion)

[MeiMei]

The question ask me to search for the shortest path to reach the target point. The fully runnable code and a map.txt with test case are in the comment.

HW requirements
You are NOT allowed to use any kind of loops in any part of your submitted code.
You are NOT allowed to use goto.
You are NOT allowed to use any global variable, or static variable like static int x.
You are NOT allowed to include any additional libraries yourself. Everything you need is already included. Especially, you can only use cstring library, and you cannot use C++ string library.
You are NOT allowed to modify any of the given function prototypes including the return types, function names, default values, and parameter lists.

Here is the task that I want to ask.

int findShortestDistance(int robot_x, int robot_y, int target_x, int target_y, int robot_energy, int robot_full_energy, 
const char map[MAP_HEIGHT][MAP_WIDTH], char temp_map[MAP_HEIGHT][MAP_WIDTH])

This recursive function finds the shortest distance from the current robot position (robot_x, robot_y) to the target position (target_x, target_y), based on the constraints of energy, chargers and blocked areas. If the robot cannot go there within the robot_energy, it returns the constant PA2_MAX_PATH and that indicates that the specified position is unreachable. But note that the robot will get fully charged again when it reaches a charger (i.e. robot_energy will be resumed to the value of robot_full_energy).

My latest attempt is in the comment and I don't know how to get further on it. Maybe my approach is just wrong :( You guys can just ignore my attempt. I really got no clue about it.

I will really appreciate your help.

[lastchance]

@MeiMei,
You would get better answers if:
(a) you post full runnable code, so that others can try it;
(b) you give full details of test cases (including inputs) and explain what you mean by "fail".

I would comment though:
- why are you storing distances in a char[][] array?
- there appear to be plenty of cases where your routine does not return anything;
- I don't see any real attempt to minimise distance.

[MeiMei]

#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;

const int MAP_WIDTH = 12;
const int MAP_HEIGHT = 12;

const int PA2_MAX_PATH = MAP_WIDTH * MAP_HEIGHT;

const int MAX_STRING_SIZE = 100;

const char AVAILABLE = ' ';
const char BLOCKED = 'B';
const char ROBOT = 'R';
const char CHARGER = 'C';
const char VISITED = 'V';
 //Not Impostant
void unifyMapLine(char target_map_line[MAP_WIDTH], const char map_line[MAP_WIDTH + 1])
{
    for (int i = 0; i < MAP_WIDTH; i++)
    {
        if (map_line[i] == '\0')
        {
            target_map_line[i] = ' ';
        }
        else
        {
            target_map_line[i] = map_line[i];
        }
    }
}
bool loadMap(const char filename[MAX_STRING_SIZE], char map_to_load[MAP_HEIGHT][MAP_WIDTH])
{
    fstream ifs(filename);
    if (ifs)
    {
        int counter = 0;
        while (!(ifs.eof() || counter >= MAP_HEIGHT))
        {
            char line[MAX_STRING_SIZE] = "";
            ifs.getline(line, MAX_STRING_SIZE);
            unifyMapLine(map_to_load[counter], line);
            counter++;
        }
        char empty_line[MAX_STRING_SIZE] = "";
        for (int padding = counter; padding < MAP_HEIGHT; padding++)
        {
            unifyMapLine(map_to_load[padding], empty_line);
        }
        return true;
    }
    return false;
}

void copyMap(char target_map[MAP_HEIGHT][MAP_WIDTH], const char original_map[MAP_HEIGHT][MAP_WIDTH])
{
    for (int i = 0; i < MAP_WIDTH; i++)
    {
        for (int j = 0; j < MAP_HEIGHT; j++)
        {
            target_map[j][i] = original_map[j][i];
        }
    }
}

void printMap(char map[MAP_HEIGHT][MAP_WIDTH])
{
    cout << "  ";
    for (int i = 0; i < MAP_WIDTH; i++)
    {
        cout << i % 10;
    }
    cout << "  " << endl;

    cout << " ";
    for (int i = 0; i < MAP_WIDTH + 2; i++)
    {
        cout << "-";
    }
    cout << endl;

    for (int j = 0; j < MAP_HEIGHT; j++)
    {
        cout << j % 10 << "|";
        for (int i = 0; i < MAP_WIDTH; i++)
        {
            cout << map[j][i];
        }
        cout << "|" << endl;
    }
    cout << " ";
    for (int i = 0; i < MAP_WIDTH + 2; i++)
    {
        cout << "-";
    }
    cout << endl;
}

void setRobot(int &robot_init_x, int &robot_init_y, int &robot_full_energy, char map[MAP_HEIGHT][MAP_WIDTH])
{
    if (map[robot_init_y][robot_init_x] == ROBOT)
        map[robot_init_y][robot_init_x] = AVAILABLE;

    cout << "Please give the x and the y of the robot, with space to separate: ";
    cin >> robot_init_x >> robot_init_y;

    map[robot_init_y][robot_init_x] = ROBOT;

    cout << "Please give battery capacity of the robot: ";
    cin >> robot_full_energy;

    return;
}

//Task 1
int findMaximumPlace(int robot_x, int robot_y, int robot_energy, int robot_full_energy, 
                     char result_map[MAP_HEIGHT][MAP_WIDTH], char temp_map[MAP_HEIGHT][MAP_WIDTH]){
   int area=0;

   if ( robot_y>=0 && robot_y<=MAP_HEIGHT-1 && robot_x>=0 && robot_x<=MAP_WIDTH-1 && result_map[robot_y][robot_x]!=BLOCKED && 
   robot_energy>=0 ) // position on map, cannot goto bloacked, last move when energy = 0 
   {  
      if ( result_map[robot_y][robot_x] == CHARGER ) // charge robot if reach charger
      robot_energy = robot_full_energy; 

      if ( result_map[robot_y][robot_x]!=VISITED )
      area++;

      result_map[robot_y][robot_x] = VISITED; // robot current position

      robot_energy --; // consume 1 energy unit for 1 possible move 

   //recursion
      area+=findMaximumPlace(robot_x, robot_y-1, robot_energy, robot_full_energy, result_map, temp_map); // up
      area+=findMaximumPlace(robot_x+1, robot_y, robot_energy, robot_full_energy, result_map, temp_map); // right
      area+=findMaximumPlace(robot_x-1, robot_y, robot_energy, robot_full_energy, result_map, temp_map); // down
      area+=findMaximumPlace(robot_x, robot_y+1, robot_energy, robot_full_energy, result_map, temp_map); // left
   }
   return area; // exit recursion
}

//Task 2
int findShortestDistance(int robot_x, int robot_y, int target_x, int target_y, int robot_energy, 
                         int robot_full_energy, const char map[MAP_HEIGHT][MAP_WIDTH], char temp_map[MAP_HEIGHT][MAP_WIDTH]){
 //the task in question
}

int main()
{
    cout << "Welcome to the cleaning program" << endl;

    char map[MAP_HEIGHT][MAP_WIDTH] = {};
    char temp_map[MAP_HEIGHT][MAP_WIDTH] = {};
    char empty_map[MAP_HEIGHT][MAP_WIDTH] = {};
    char result_map[MAP_HEIGHT][MAP_WIDTH] = {};

    int robot_full_energy = 10;

    int robot_x = 0;
    int robot_y = 0;
    int robot_energy = robot_full_energy;

    int choice = 0;
    int int_result = 0;
    int dest_x = 0, dest_y = 0;

    char result_sequence[MAX_STRING_SIZE] = "";

    bool map_loaded = false;

    do
    {
        cout << "Please select from the following options:" << endl;
        cout << "0: Load map" << endl;
        if (map_loaded)
        {
            cout << "1. Print original map" << endl;
            cout << "2. Print robot details" << endl;
            cout << "3. Display the maximum range for the robot in the current place:" << endl;
            cout << "4. Find the shortest distance from current position to a designated position" << endl;
            cout << "5. Find the shortest distance and the shortest path from current position to a designated position" << endl;
            cout << "6. Find the position of the farthest charger and the shortest distance from that charger" << endl;
        }
        cout << "-1. Exit program" << endl;
        cout << "Please enter your choice: ";

        cin >> choice;
        switch (choice)
        {
        case 0:
            char filename[MAX_STRING_SIZE];
            cout << "Please type the file you want to use: ";
            cin >> filename;

            if (loadMap(filename, map))
            {
                printMap(map);
                map_loaded = true;
                setRobot(robot_x, robot_y, robot_full_energy, map);
                robot_energy = robot_full_energy;
                printMap(map);
            }
            else
            {
                cout << "Cannot load map. Please check if the file exists." << endl;
            }
            break;
        case 1:
            printMap(map);
            break;

        case 2:
            cout << "Robot position: (" << robot_x << "," << robot_y << ")" << endl;
            cout << "Robot energy: " << robot_energy << "/" << robot_full_energy << endl;
            break;
        case 3:
            copyMap(result_map, map);
            copyMap(temp_map, empty_map);
            int_result = findMaximumPlace(robot_x, robot_y, robot_energy, robot_full_energy, result_map, temp_map);
            cout << int_result << endl;
            cout << "The result map will be:" << endl;
            printMap(result_map);
            break;
        case 4:
            cout << "Please enter the target x and y, separated by space: ";
            cin >> dest_x >> dest_y;
            copyMap(temp_map, empty_map);
            int_result = findShortestDistance(robot_x, robot_y,
                                              dest_x, dest_y, robot_energy, robot_full_energy, map, temp_map);

            if (int_result >= PA2_MAX_PATH)
            {
                cout << "The destination is unreachable." << endl;
            }
            else
            {
                cout << int_result;
                
            }
            break;
        }
        cout << endl;
    } while (choice != -1);
    cout << "Program ends." << endl;
    return 0;
}

[MeiMei]

BBBBBBBBBBB
BBBBBBBBB
BBB BBB B B
B BB
B B B BB
B
C BB
B C B
BBBB BBBBBB
B C BB
BBBBB B
BBBBBB

The upper part is the map.txt that used as a test case and loaded to the program.

test case: if robot set at 5,5 with battery size 5
If the target is (5, 5) (that means the same with the robot), the return value is 1.
If the target is (5, 6), the return value is 2.
If the target is (6, 6), the return value is 3.
If the target is (6, 7), the return value is 4. //fail
If the target is (7, 5), the return value is 3.
If the target is (3, 3), the return value is 5.
If the target is (5, 3), the return value is 5.
If the target is (2, 4), the return value is MAX_PATH PA2_MAX_PATH , that means it is unreachable (as it is BLOCKED). //fail
If the target is (5, 9), the return value is 7, as to go there, the robot has to use the charger in (4, 9). //fail
If the target is (3, 11), the return value is 11, as to go there, the robot has to use the charger in (4, 9). //fail

[MeiMei]

@lastchance (6059)
I post a full runnable code in the comment, with the map used for testing. Sorry that it is quite lengthy. Thank you so much.

I haven't try the test case that the target need a charger or is unreachable yet.

When I try to debugged the failed test case as above (6,7) cannot get the result 4 by recursion, it will just return 5,and get even smaller values like 3 or 2, without returning it. However, the other cases can sucessfully get the answer.

For the comments:
- why are you storing distances in a char[][] array?
The function name and parameters are given and it is required that we CANNOT modify them. At first I try to add a statement int(temp_map) inside the function but it fail as it can't do recursion anymore.

- there appear to be plenty of cases where your routine does not return anything;
The task is quite challenging to me, and I don't know how to confirm that all the direction have been passed through before returning a value.

- I don't see any real attempt to minimise distance.
As one move cost 1 energy unit, I try to figure out the distance from the position by full_energy minus current_energy. After reach target, store this into target position. Then keep recursing on other direction to see if there are other path to target. If there are other path, then compare them to store the smaller distance into the temp_map[target_position].

I am not sure about whether this method is workable or not but I think it is already the closest one I've made :(

Thank you again.

[MeiMei]

emmm, I thought the condition at the bottom means is if 4 direction all can't reach target, then return unreachable, else return the distance. But it is apparently not after I try to run the program.
What is wrong with that statement?

int findShortestDistance(int robot_x, int robot_y, int target_x, int target_y, int robot_energy, 
                         int robot_full_energy, const char map[MAP_HEIGHT][MAP_WIDTH], char temp_map[MAP_HEIGHT][MAP_WIDTH]){
   
   int distance = robot_full_energy-robot_energy+1;
   
   if(robot_y>=0 && robot_y<=MAP_HEIGHT-1 && robot_x>=0 && robot_x<=MAP_WIDTH-1 && map[robot_y][robot_x]!=BLOCKED && 
   robot_energy>=0)
   {
      if ( !temp_map[robot_y][robot_x] )
      temp_map[robot_y][robot_x]=distance+48;
      else if ( distance+48 < int(temp_map[robot_y][robot_x]) )
      temp_map[robot_y][robot_x]=distance+48;

      if ( temp_map[target_y][target_x] )
      return temp_map[target_y][target_x]-48;
      
      //error (6,7) case
      //not yet consider charger
      robot_energy--;
      if (!findShortestDistance( robot_x, robot_y-1, target_x, target_y, robot_energy, robot_full_energy, map, temp_map) &&
      !findShortestDistance( robot_x+1, robot_y, target_x, target_y, robot_energy, robot_full_energy, map, temp_map) &&
      !findShortestDistance( robot_x, robot_y+1, target_x, target_y, robot_energy, robot_full_energy, map, temp_map) &&
      !findShortestDistance( robot_x-1, robot_y, target_x, target_y, robot_energy, robot_full_energy, map, temp_map))
      return PA2_MAX_PATH; // means unreachable 
      return temp_map[target_y][target_x]-48;
   }
   return false;
}

[ne555]

¿what's the purpose of `temp_map'? It seems to be storing "distances" but for some weird reason you add 48 to each cell.


> find the shortest distance from the current position to the target position on a 2D map.
from your code and the charger cells, it seems that you don't want the shortest path, but the robot to reach the target with the largest energy reserve.
or at least, define your distance properly.

> if there's any method to record the robot reach a charger
robot_energy = robot_full_energy;

> Maybe my approach is just wrong :(
explain your approach, perhaps it's just badly implemented (in plain English, please)

[MeiMei]

@ne555
temp_map is an empty char array that has the same size as map. As I want to store an int variable into it as an record, ASCII code of '0' is 48, so I add 48 to each cell in order to change int into a characters

In the program, we can set up the position and robot_full_energy. if we input 5 as maximum energy, initially the energy unit of robot is 5/5.

The assignment only allows local variables and loops are not allowed. I guess there will be different path to the target and the program need to compare them, everytime the robot reach the target. So instead of local variables, I try to use parameters to define distance.

As I mentioned as each move consume a energy unit, so I guess by looking for the largest energy reserve can also derive get the shortest distance.

My English is not that good. If I didn't express things clearly, please just let me know and I will try my best to explain.

[mbozzi]

Consider something like this. Hopefully it will be useful even though it does not meet all the requirements of your assignment.

# 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); 
}

Live demo here:
https://godbolt.org/z/z8n87j67K

[MeiMei]

Thank you for all your help. This task is solved! I am going to move on to the next task which is recording the path sequence of the shortest path and finding the farthest path. Wish me luck.

[dhayden]

This task is harder than it appears. Consider this map:

  0 1 2 3 4 5 6 7 8 9 0 1
 --------------------------
0|B B B       B B B B B   |
1|B B B       B B B       |
2|B B B   B B B   B   B   |
3|B   B     C             |
4|B   B   B   B B         |
5|B   R                   |
6|C   B B     B           |
7|B B C       B           |
8|B B B B   B B B         |
9|B   C     B             |
0|B B B     B             |
1|B B B                   |
 --------------------------
  0 1 2 3 4 5 6 7 8 9 0 1

The robot is at (2,5). If max power is 10, then here is the max range,as correctly computed by your code:

  0 1 2 3 4 5 6 7 8 9 0 1
 --------------------------
0|B B B V V V B B B B B V |
1|B B B V V V B B B V V V |
2|B B B V B B B V B V B V |
3|B V B V V V V V V V V V |
4|B V B V B V B B V V V V |
5|B V V V V V V V V V V V |
6|V V B B V V B V V V V V |
7|B B V V V V B V V V V V |
8|B B B B V B B B V V V   |
9|B V V V V B V V V V     |
0|B B B V V B V V V V     |
1|B B B V V V V V V V V   |
 --------------------------
  0 1 2 3 4 5 6 7 8 9 0 1

Consider how to get to (10,11). You have to go to (4,7), then left to (2,7) to get the charger, and the backtrack to (4,7) and continue from there. You could do the same thing with the charger at (9,2) also. Here is the path shown with '.'s. I left the "C" for the charger, but the path visits it:

  0 1 2 3 4 5 6 7 8 9 0 1
 --------------------------
0|B B B       B B B B B   |
1|B B B       B B B       |
2|B B B   B B B   B   B   |
3|B   B     C             |
4|B   B   B   B B         |
5|B   R . .               |
6|C   B B .   B           |
7|B B C . .   B           |
8|B B B B . B B B         |
9|B   C   . B             |
0|B B B   . B             |
1|B B B   . . . . . . .   |
 --------------------------
  0 1 2 3 4 5 6 7 8 9 0 1

Backtracking like this is somewhat complicated to do in the code.

[mbozzi]

I don't know if your comment is addressed to me but the program I wrote correctly handles this case. It is not an efficient algorithm, but it is handled properly.

First assume the robot starts with a full battery. Imagine a graph whose vertices consist of the robot's initial position, the target position, and all chargers. Than there's an edge between two nodes if and only if there's a path of distance d <= max_energy between them. The edge weight is the distance d.

The original problem is finding the shortest path through this undirected graph.

One key observation was that the state of the simulation doesn't change on subsequent visits to a charger, except that the total distance traversed is possibly greater. So there's no reason to ever revisit a charger.

[dhayden]

MBozzi, no, my comment wasn't addressed at your program. It was addressed at my own failed for attempts :). Sorry, I should have made that clear. I wanted to try solving it without looking at what others had done. I'll put my solution here shortly.

[dhayden]

Here's my code. It follows the original restrictions, which make the code harder than it could be. Paste this into the original program to run it.

//Task 2
int findShortestDistance(int robot_x, int robot_y, int target_x, int target_y, int robot_energy, 
                         int robot_full_energy, const char map[MAP_HEIGHT][MAP_WIDTH], char temp_map[MAP_HEIGHT][MAP_WIDTH]){
   
    // "map" is the map to navigate.
    // temp_map cells contain:
    //   - Zero if the cell hasn't been considered yet
    //   - VISITED if the cell is on the path we're currently considering (and thus would form a loop)

    if(robot_y < 0 || robot_y >= MAP_HEIGHT || robot_x < 0 || robot_x >= MAP_WIDTH // out of bounds
       || map[robot_y][robot_x] == BLOCKED // blocked
       || temp_map[robot_y][robot_x] == VISITED   // already went here. Going here again is a loop.
       || robot_energy < 0) {			  // died
	return PA2_MAX_PATH;
    }

    if (robot_y == target_y && robot_x == target_x) {
	return 0;		// you have arrived!
    }

    int result;
    if (map[robot_y][robot_x] == CHARGER) {
	// If you hit a charger, then the shortest path may involve
	// backtracking.  To handle this case, we create a new map without
	// the charger and start a new path from the current location.
	// Then return the distance from here, starting with full energy.
	char newMap[MAP_HEIGHT][MAP_WIDTH];
	char newPath[MAP_HEIGHT][MAP_WIDTH] = {};
	copyMap(newMap, map);
	newMap[robot_y][robot_x] = ROBOT; // so the charger can't be used again
	result = findShortestDistance(robot_x, robot_y, target_x, target_y, robot_full_energy, robot_full_energy, newMap, newPath);
    } else {
	// Otherwise, mark the current position as visited. Then the shortest path from here is
	// 1 + (shortest path from my neighbors)
	temp_map[robot_y][robot_x] = VISITED;
	result = findShortestDistance( robot_x, robot_y-1, target_x, target_y, robot_energy-1, robot_full_energy, map, temp_map);
	result = min(result, findShortestDistance( robot_x+1, robot_y, target_x, target_y, robot_energy-1, robot_full_energy, map, temp_map));
	result = min(result, findShortestDistance( robot_x, robot_y+1, target_x, target_y, robot_energy-1, robot_full_energy, map, temp_map));
	result = min(result, findShortestDistance( robot_x-1, robot_y, target_x, target_y, robot_energy-1, robot_full_energy, map, temp_map));
	temp_map[robot_y][robot_x] = 0; // make it available again since we're returning.
	if (result != PA2_MAX_PATH) {
	    ++result; 			// because it takes one move to get to the neighbor
	}
    }
    return result;
}

Welcome to the cleaning program
Please select from the following options:
0: Load map
-1. Exit program
Please enter your choice: 0
Please type the file you want to use: map.txt
  0 1 2 3 4 5 6 7 8 9 0 1
 --------------------------
0|B B B       B B B B B   |
1|B B B       B B B       |
2|B B B   B B B   B   B   |
3|B   B     C             |
4|B   B   B   B B         |
5|B                       |
6|C   B B     B           |
7|B B C       B           |
8|B B B B   B B B         |
9|B   C     B             |
0|B B B     B             |
1|B B B                   |
 --------------------------
  0 1 2 3 4 5 6 7 8 9 0 1
Please give the x and the y of the robot, with space to separate: 2 5
Please give battery capacity of the robot: 10
  0 1 2 3 4 5 6 7 8 9 0 1
 --------------------------
0|B B B       B B B B B   |
1|B B B       B B B       |
2|B B B   B B B   B   B   |
3|B   B     C             |
4|B   B   B   B B         |
5|B   R                   |
6|C   B B     B           |
7|B B C       B           |
8|B B B B   B B B         |
9|B   C     B             |
0|B B B     B             |
1|B B B                   |
 --------------------------
  0 1 2 3 4 5 6 7 8 9 0 1

Please select from the following options:
0: Load map
1. Print original map
2. Print robot details
3. Display the maximum range for the robot in the current place:
4. Find the shortest distance from current position to a designated position
5. Find the shortest distance and the shortest path from current position to a designated position
6. Find the position of the farthest charger and the shortest distance from that charger
-1. Exit program
Please enter your choice: 4
Please enter the target x and y, separated by space: 10 11
The destination is 18 moves away from 2, 5

[mbozzi]

@dhayden It definitely took me more than one try as well. Interesting that our solutions are mostly the same. I feel like there's a better algorithm to solve this.