SPOJ KATHTHI - KATHTHI(01BFS)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
//#define int long long 
using namespace std;
const int MAXN = 1001;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M;
struct Node {
    int x, y, s;
};
deque<Node> q;
int dis[MAXN][MAXN], xx[] = {-1, +1, 0, 0}, yy[] = {0, 0, -1, +1};
char s[MAXN][MAXN];
void OneZeroBFS() {
    q.push_back((Node) {1, 1, 0});
    while(!q.empty()) {
        Node p = q.front(); q.pop_front();
        for(int i = 0; i < 4; i++) {
            int wx = p.x + xx[i], wy = p.y + yy[i];
            int w = (s[wx][wy] != s[p.x][p.y]);
            if(dis[wx][wy] > dis[p.x][p.y] + w && (wx > 0 && wy > 0 && wx <= N && wy <= M))
                dis[wx][wy] = dis[p.x][p.y] + w,
                w == 1 ? q.push_back((Node) {wx, wy, w}) : q.push_front((Node) {wx, wy, w});
        }
    }
}
main() {
    int QwQ = read();
    while(QwQ--) {
        memset(dis, 0xf, sizeof(dis));
        dis[1][1] = 0;
        N = read(); M = read();
        for(int i = 1; i <= N; i++)    
            scanf("%s", s[i] + 1);
        OneZeroBFS();
        printf("%d\n", dis[N][M]);
    }
    return 0;
}
/*
4
2 2
aa
aa
2 3
abc
def
6 6
akaccc
aaacfc
amdfcc
aokhdd
zyxwdp
zyxwdd
5 5
abbbc
abacc
aaacc
aefci
cdgdd
*/