## Submission

typedef array<int,3> AI3; // cost, x, y (x, y is the current position)
class Solution {
int visited[101][101];
public:
int minCost(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
priority_queue<AI3, vector<AI3>, greater<>> pq;
pq.push({0, 0, 0});
vector<pair<int, int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
while(!pq.empty()) {
auto [cost, x, y] = pq.top();
pq.pop();
if(visited[x][y]) continue;
visited[x][y] = 1;
if(x == m - 1 && y == n -1) return cost;
for(auto d: dir) {
int newX = x + d.first;
int newY = y + d.second;
if(newX < 0 || newX >= m || newY < 0 || newY >= n) continue;
pq.push({cost + (d != dir[grid[x][y]-1]), newX, newY});
}
}
return 0;
}
};