Re: [閒聊] 每日leetcode已回收

看板Marginalman作者oinishere (是oin捏)時間1年前 (2024/05/15 16:21)推噓3(3推 0噓 6→)

留言9則, 8人參與討論串223/1548 (看更多)

※ 引述《osopopototo (我是垃圾哦)》之銘言： : -- 給一個nxn的矩陣，裡面包含0和1 求從(0,0)出發到(n-1,n-1)離所有1最遠的路徑，其中與任一1最近的距離距離定義為曼哈頓距離(|x1-x2|+|y1-y2|) 思路: 因為要知道最安全的路的最小距離所以就要先把每個地方的安全距離找出來然後再用bfs找路一開始我是直接硬幹每個0都bfs 時間當然炸了改成用1bfs 竟然也炸了然後我就想幹你娘咧你媽的什麼陰間題目操機掰就突然發現每次用1慢慢bfs 都會重複路過已經比過的地方所以如果可以一起比的話就很棒所以我就直接把所有1一起放進去我的pq 讓所有1一起bfs 就成功了雖然我的速度1500多毫秒只beat 10% 不過沒關係我成功了然後我把題目餵給gpt 他500毫秒幹你娘咧我要被取代了 class Solution { public: vector<vector<int>> disgrid; int maximumSafenessFactor(vector<vector<int>>& grid) { if(grid[0][0] == 1)return 0; int n = grid.size(); int m = grid[0].size(); if(grid[n-1][m-1] == 1)return 0; disgrid.resize(n,vector<int>(m,10000)); vector<vector<bool>> passs(n,vector<bool>(m,0)); priority_queue< pair<int ,pair<int,int>> , vector<pair<int ,pair<int,int >>> , greater<pair<int ,pair<int,int>> >> saves; for(int i = 0 ; i < n ; i ++ ) { for(int j = 0 ; j < m ; j ++) { if(grid[i][j]==0)continue; saves.push({0,{i,j}}); } } while(!saves.empty()) { int ni = saves.top().second.first; int nj = saves.top().second.second; if(ni<0 || ni==n || nj<0 || nj==m){ saves.pop(); continue; } int diss = saves.top().first; saves.pop(); if(passs[ni][nj])continue; passs[ni][nj] = 1; disgrid[ni][nj] = min(disgrid[ni][nj] , diss); saves.push({diss+1 ,{ni-1,nj}}); saves.push({diss+1 , {ni+1,nj}}); saves.push({diss+1 , {ni,nj-1}}); saves.push({diss+1 , {ni,nj+1}}); } vector<vector<bool>> pass(n,vector<bool>(m,0)); priority_queue<pair<int , pair<int,int>>> save; save.push({disgrid[0][0] , {0,0}}); int mindis = disgrid[0][0]; while(!save.empty()) { int ni = save.top().second.first; int nj = save.top().second.second; // cout << ni <<"," << nj<<endl; if(ni<0 || ni>=n || nj<0 || nj>=m){ // cout<<"88"<<endl; save.pop(); continue; } int dis = disgrid[ni][nj]; // cout << ni <<"," << nj<<" : " << dis <<endl; save.pop(); if(pass[ni][nj])continue; pass[ni][nj] = 1; mindis = min(mindis,dis); if(ni == n-1 && nj == m-1) { break; } if(ni-1 >= 0 )save.push({disgrid[ni-1][nj] , {ni-1,nj}}); if(ni+1 != n)save.push({disgrid[ni+1][nj] , {ni+1,nj}}); if(nj-1 >= 0)save.push({disgrid[ni][nj-1] , {ni,nj-1}}); if(nj+1 != m)save.push({disgrid[ni][nj+1] , {ni,nj+1}}); } return mindis; } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.142.93 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715761293.A.A8A.html

→

argorok

05/15 16:22, 1年前 , 1^F

05/15 16:22, 1^F

→

oinishere

05/15 16:22, 1年前 , 2^F

05/15 16:22, 2^F

→

SiranuiFlare

05/15 16:23, 1年前 , 3^F

05/15 16:23, 3^F