Untitled

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl "\n"
 
const double PI = 3.14159265358979;
const ll INF =  1e9 + 7;
const ll MOD = 1e9 + 7;
const ll nax = 2505;
const int LOG = 25;


int dx[4] = {0, 0, 1, -1}; // right, left, down, up 
int dy[4] = {1, -1, 0, 0};

// {x, y, wt}
// right: 1
// left: 2
// down: 3
// up: 4
vector<vector<int> > getNeighbours(int sx, int sy, vector<vector<int> > &grid) {
    vector<vector<int> > neighbours;
    int n = grid.size();
    int m = grid[0].size();

    for (int k = 0; k < 4; k++) {
        int ex = sx + dx[k];
        int ey = sy + dy[k];

        if (!(ex >= 0 && ex < n && ey >= 0 && ey < m)) {
            continue;
        }

        neighbours.push_back({ex, ey, grid[sx][sy] != (k + 1)});
    }

    return neighbours;
}


vector<vector<int> > bfs01(int sx, int sy, vector<vector<int> > &grid) {
    int n = grid.size();
    int m = grid[0].size();

    vector<vector<int> > cost(n, vector<int> (m, INF));
    vector<vector<bool> > visited(n, vector<bool> (m, false));    
    deque<pair<int, int> > dq;

    cost[sx][sy] = 0;
    dq.push_back({sx, sy});

    while(!dq.empty()) {
        pair<int, int> curr = dq.front();
        dq.pop_front();

        int currX = curr.first;
        int currY = curr.second;

        if (visited[currX][currY]) continue;
        visited[currX][currY] = true;

        for (auto &neigh: getNeighbours(currX, currY, grid)) {
            int neighX = neigh[0];
            int neighY = neigh[1];
            int neighWt = neigh[2];

            if (cost[neighX][neighY] > cost[currX][currY] + neighWt) {
                cost[neighX][neighY] = cost[currX][currY] + neighWt;
            }

            if (neighWt == 0) {
                dq.push_front({neighX, neighY});
            } else {
                dq.push_back({neighX, neighY});
            }
        }
    }

    return cost;
}

void solve() {
    int n, m;
    cin >> n >> m;

    vector<vector<int> > grid(n, vector<int> (m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grid[i][j];
        }
    }

    vector<vector<int> > cost = bfs01(0, 0, grid);
    cout << cost[n - 1][m - 1];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // int t; cin >> t; while(t--)
    solve();
    return 0;
}