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 39 40
| class Solution { public: int n, m; struct point{ int x, y, c; point(){} point(int x, int y, int c):x(x), y(y), c(c){} friend bool operator < (point a, point b) { return a.c > b.c; } }; bool is_ok(point p) { return (p.x >= 0 && p.x < n && p.y >= 0 && p.y < m); } int minCost(vector<vector<int>>& grid) { priority_queue<point> pq; int vis[100][100]; memset(vis, -1, sizeof vis); int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; n = grid.size(), m = grid[0].size(); point cur = point(0, 0, 0); pq.push(cur); vis[0][0] = 0; while(!pq.empty()) { cur = pq.top(); pq.pop(); for(int i = 0; i < 4; i++) { point nxt = cur; nxt.x += nx[i]; nxt.y += ny[i]; if(!is_ok(nxt)) continue; if(grid[cur.x][cur.y] != i + 1) nxt.c++; if(vis[nxt.x][nxt.y] == -1 || nxt.c < vis[nxt.x][nxt.y]) { vis[nxt.x][nxt.y] = nxt.c; pq.push(nxt); } } } return vis[n-1][m-1]; } };
|