Untitled

 avatar
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