Para este problema vamos usar uma ideia parecida com o algoritmo de Dijsktra (Menor caminho). Podemos considerar que o mapa da prisão é um grafo, onde cada aresta liga apenas elementos ao norte, sul, leste ou oeste, e o peso de cada aresta é $$0$$ ou $$1$$. $$0$$ quando $$map[x_1][y_1] = map[x_2][y_2]$$ e $$1$$ caso contrário.
A modificação necessária no Dijkstra é que: sempre que vamos inserir um elemento na fila, olhamos se a aresta que liga ele é $$0$$ ou $$1$$, caso seja $$0$$ inserimos o elemento no início da fila e caso contrário inserimos no final. Essa pequena modificação só é valida quando as arestas possuem apenas peso $$0$$ ou $$1$$. Note que dessa maneira sempre matemos a fila ordenada, ou seja, sempre chegaremos em cada vértice na menor distância possível, o que garante o funcionamento do Dijkstra. Dessa forma conseguimos reduzir a complexidade do algoritmo de Dijkstra de $$\mathcal{O}(N^2\cdot log(N))$$ para $$\mathcal{O}(N^2)$$
Código comentado:
https://gist.github.com/lawrencefmm/d3ca3269d0ae87e26d3adde80786db7e