Re: [閒聊] 每日leetcode

看板Marginalman作者oin1104 (是oin的說)時間8月前 (2025/03/28 18:22)推噓1(1推 0噓 2→)

題目有一個陣列每次都從左上角出發如果當前數字比較大的話就可以過去請問對於每個queries 的數字他們能走多少個格子思路如果每個queries 都走一次bfs 一定會超時但是因為每次queries 都是從左上角所以可以確定 queries數字大的一定可以走到queries 數字小的地方就可以發現只要sort queries 之後每個queries 都可以繼承前一個走過的bfs 然後用對應的idx塞回去就好了 class Solution { public: vector<int> maxPoints(vector<vector<int>>& grid, vector<int>& queries) { int n = grid.size(); int m = grid[0].size(); int qn = queries.size(); vector<pair<int,int>> que_i(qn); vector<vector<int>> passed(n,vector<int>(m)); for(int i = 0 ; i < qn ; i ++)que_i[i] = {queries[i],i}; sort(que_i.begin() , que_i.end()); vector<int> res(qn); // val i j priority_queue<pair<int,pair<int,int>> , vector<pair<int,pair<int,int>>> , greater<pair<int,pair<int,int>>>> pq; pq.push({grid[0][0] , {0,0}}); passed[0][0] = 1; int cnt = 0; // for(int i = 0 ; i < qn ; i ++)cout << que_i[i].first << " "; for(int i = 0 ; i < qn ; i ++) { int now = que_i[i].first; int idx = que_i[i].second; // cout << now << " " << idx << " \n"; while(!pq.empty() && pq.top().first < now) { cnt ++; int gi = pq.top().second.first; int gj = pq.top().second.second; // cout << pq.top().first << " " ; pq.pop(); if(gi-1 >= 0 && passed[gi-1][gj] == 0) { pq.push({grid[gi-1][gj] , {gi-1,gj}}); passed[gi-1][gj] = 1; } if(gi+1 < n && passed[gi+1][gj] == 0) { pq.push({grid[gi+1][gj] , {gi+1,gj}}); passed[gi+1][gj] = 1; } if(gj-1 >= 0 && passed[gi][gj-1] == 0) { pq.push({grid[gi][gj-1] , {gi,gj-1}}); passed[gi][gj-1] = 1; } if(gj+1 < m && passed[gi][gj+1] == 0) { pq.push({grid[gi][gj+1] , {gi,gj+1}}); passed[gi][gj+1] = 1; } } res[idx] = cnt; // cout << endl; } return res; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.18.82 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1743157343.A.971.html

推

JIWP

03/28 18:23, 8月前 , 1^F

03/28 18:23, 1^F

→

Rushia

03/28 18:30, 8月前 , 2^F

03/28 18:30, 2^F

→

sixB

03/29 05:30, 8月前 , 3^F

03/29 05:30, 3^F