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 é 
ou 
. quando ![map[x_1][y_1] = map[x_2][y_2]](https://i0.wp.com/noic.com.br/wp-content/plugins/latex/cache/tex_af065dc0fc3d6d0e3b66b71aab9ed9d8.gif?ssl=1)
e 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 é ou , caso seja 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 ou . 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 
para 
Código comentado:
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <bits/stdc++.h> | |
| using namespace std; | |
| #define x first | |
| #define y second | |
| typedef pair<int, pair<int, int>> pii; | |
| const int maxn = 1e3 + 10; | |
| int dx[4] = {1, 0, 0, -1}; // apenas para simplificar o deslocamento no grid 2D | |
| int dy[4] = {0, 1, -1, 0}; | |
| int dist[maxn][maxn], vis[maxn][maxn], R, C; | |
| char mat[maxn][maxn]; | |
| inline void dijkstra() | |
| { | |
| memset(dist, 0x3f3f3f3f, sizeof(dist)); | |
| memset(vis, 0, sizeof(vis)); | |
| dist[0][0] = 0; | |
| deque<pii> q; // usamos a estrutura de dados deque (double-ended queue) | |
| // pois ela nos permite inserir elementos no inicio e no final da fila. | |
| q.push_front({0, {0, 0}}); // insiro o vertice (0, 0) | |
| while(!q.empty()) // enquanto houver elementos na fila | |
| { | |
| auto a = q.front(); // pego o elemento da frente | |
| q.pop_front(); // apago; | |
| int xat = a.y.x, yat = a.y.y; // xat, ou x atual só para guardar o x do elemento da frente | |
| // o mesmo vale para o yat | |
| if(vis[xat][yat]) continue; // se (xat, yat) ja foi visitado, nao o visito novamente | |
| vis[xat][yat] = true; // caso contrario marco (xat, yat) como ja visitado | |
| for(int i = 0; i < 4; i++) // percorro todas as 4 posicoes adjacentes | |
| { | |
| int nx = xat + dx[i], ny = yat + dy[i]; // nx é o x da posicao adjacente e ny o y | |
| if(nx >= R or nx < 0 or ny >= C or ny < 0) continue; // nao rodo o codigo caso a posicao esteja fora do grid | |
| int distancia = (mat[xat][yat] != mat[nx][ny]); // variavel para guardar o peso da aresta | |
| // se mat[xat][yat] for diferente de mat[nx][ny] entao distancia vale 1, e 0 caso sejam iguais | |
| if(dist[nx][ny] > dist[xat][yat] + distancia) // se achei uma distancia menor | |
| { | |
| dist[nx][ny] = dist[xat][yat] + distancia; // atualizo a distancia | |
| if(distancia == 0) q.push_front({dist[nx][ny], {nx, ny}}); // se p eso da aresta é zero | |
| // o elemento é inserido no inicio | |
| else q.push_back({dist[nx][ny], {nx, ny}});// se o peso é 1, no final | |
| } | |
| } | |
| } | |
| } | |
| int main() | |
| { | |
| ios::sync_with_stdio(false), cin.tie(nullptr); | |
| int t; | |
| cin >> t; | |
| while(t–) | |
| { | |
| cin >> R >> C; | |
| for(int i = 0; i < R; i++) | |
| for(int j = 0; j < C; j++) | |
| cin >> mat[i][j]; | |
| dijkstra(); | |
| cout << dist[R – 1][C – 1] << "\n"; | |
| } | |
| } |