prisao.cpp

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