One way to solve your problem is to first represent your 2D array as a graph, where each letter is a node, and there exists an edge between two nodes if the letter they represent are neighbor in the array, and these letters are different (one A
and one B
).
Then all you have to do is to use a classical shortest path algorithm, such as Dijkstra's, or A*, to find the shortest path between two nodes of your graph. This will be equivalent to finding the shortest path between two letters of your array.
Edit:
here is a pseudocode to answer the question you asked in the comment.
nodes = init_a_2d_array_of_graph_nodes(ARRAY_WIDTH, ARRAY_HEIGHT)
for i from 1 to ARRAY_WIDTH:
for j from 1 to ARRAY_HEIGHT:
if i < ARRAY_WIDTH and array[i][j] != array[i+1][j]:
add_edge(nodes[i][j], nodes[i+1][j])
if j < ARRAY_HEIGHT and array[i][j] != array[i][j+1]:
add_edge(nodes[i][j], nodes[i][j+1])
First, you need to initialize a graph structure. If you don't know how to do that, check online, there must be plenty of ways to do it, it is rather simple.
Then, you need to create one node for each letter in your array. It is convenient to store these node in a 2D array as well, so you can find out easily which letter of your array corresponds to which node in your graph.
Then, for all neighbor letters, you check if these letters are different (that is what is checked in the 2 if
conditions). If it is the case, you connect the two nodes with an edge.
After that, you'll need to run a shortest path algorithm on your graph, between your source node and destination node. Dijkstra's algorithm is the best way to get started with shortest path algorithm, it is the most widely used, and is fast enough in most of the situations you'll encounter.
Finally, once you have your path, you need to retrieve the index (row and column) of the nodes of your graph, that will give you the corresponding path in your letters array.
Feel free to comment again if there is still something you do not understand.