Untitled

#include <iostream>

using namespace std;

int t, n, m;
int sx, sy, ex, ey;
const int MN = 250;
int grid[MN][MN];
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int memo[MN][MN][5];

struct Queue {
    int q[MN*MN];
    int front, rear;

    Queue() {
        front = rear = -1;
    }

    void init() {
        front = rear = -1;
    }

    bool isEmpty() {
        return front == rear;
    }

    void push(int num) {
        q[++rear] = num;
    }

    int pop() {
        return q[++front];
    }
};

Queue mq_x, mq_y, mq_p;

int dp(int s_x, int s_y) {
    mq_x.init();
    mq_y.init();

    mq_x.push(s_x);
    mq_y.push(s_y);
    mq_p.push(0);
    int ans = (int)1e9;

    while (!mq_x.isEmpty()) {
        int x = mq_x.pop();
        int y = mq_y.pop();
        int p = mq_p.pop();

        for (int i = 0; i < n; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (0 <= nx && nx < n && 0 <= ny && ny < m && !grid[nx][ny] && memo[nx][ny][i + 1] == -1) {
                memo[nx][ny][i + 1] = (p != (i + 1)) + memo[x][y][p];

                if (nx == ex && ny == ey) {
                    ans = min(ans, memo[nx][ny][i + 1]);
                }
                else {
                    mq_x.push(nx);
                    mq_y.push(ny);
                    mq_p.push(i + 1);
                }
            }
        }
    }

    return ans;
}

int main() {
    cin >> t;
    for (int test_case = 1; test_case <= t; ++test_case) {
        cin >> m >> n;
        cin >> sy >> sx >> ey >> ex;

        for (int i = 0; i < n; ++i) {
            string s;
            cin >> s;
            for (int j = 0; j < m; ++j) {
                grid[i][j] = s[j] - '0';

                for (int p = 0; p < 5; ++p) {
                    memo[i][j][p] = -1;
                }
            }
        }
        sy--;
        sx--;
        ey--;
        ex--;
        int ans = dp(sx, sy);
        cout << ((ans == 1e9) ? -1 : ans) << '\n';
    }
    return 0;
}