推 JIWP: 我好崇拜你 03/28 18:23
→ Rushia: 你好優秀 03/28 18:30
→ sixB: 我也先sort還是tle 我真的很崇拜你 03/29 05:30
題目
有一個陣列
每次都從左上角出發
如果當前數字比較大的話
就可以過去
請問
對於每個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