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:
| #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"; | |
| } | |
| } |
