1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
using PII = pair<int, int>;
const int N = 1001;
int t, R, C, dist[N][N], ds[5] = {1, 0, -1, 0, 1};
char g[N][N];
int bfs() {
memset(dist, 0x3f, sizeof(dist));
dist[0][0] = 0;
deque<PII> q;
q.emplace_back(0, 0);
while (q.size()) {
auto [x, y] = q.front(); q.pop_front();
for (int i = 0; i < 4; ++i) {
int nx = x + ds[i], ny = y + ds[i + 1];
if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
int d = g[x][y] != g[nx][ny];
if (dist[nx][ny] > dist[x][y] + d) {
dist[nx][ny] = dist[x][y] + d;
if (d) q.emplace_back(nx, ny);
else q.emplace_front(nx, ny);
}
}
}
return dist[R - 1][C - 1];
}
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d", &R, &C);
for (int i = 0; i < R; ++i) scanf("%s", g[i]);
printf("%d\n", bfs());
}
return 0;
}
|