Untitled
unknown
plain_text
6 months ago
1.1 kB
3
Indexable
#include <vector> #include <queue> using namespace std; int dx[3] = {-1, 0, 1}; int dy[3] = {1, 1, 1}; int dem[1001][1001]; //struct cmp { // bool operator()(pair<int, int>a, pair<int, int> b) { // if(a.first == b.first) return a.second > b.second; // return a.first > b.first; // } //}; class Solution { public: int maxMoves(vector<vector<int>>& grid) { int res = 0; int n = grid.size(); for(int i=0; i<n; i++) { priority_queue<pair<int, int>, vector<pair<int, int>>> pq; pq.push(make_pair(i, 0)); memset(dem, 0, n + 1); while(!pq.empty()) { int curX = pq.top().first; int curY = pq.top().second; pq.pop(); bool check = false; for(int k=0; k<3; k++) { int nx = curX + dx[k]; int ny = curY + dy[k]; if(nx >=0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] > grid[curX][curY]) { pq.push(make_pair(nx, ny)); dem[nx][ny] = dem[curX][curY] + 1; check = true; } } if(!check) { res = dem[curX][curY] > res ? dem[curX][curY] : res; } } } return res; } };
Editor is loading...
Leave a Comment