※ 引述 《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-website.tw), 來自: 61.230.142.93 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1715761293.A.A8A

→ argorok: 就說別捲了 捲不過gpt 05/15 16:22

→ oinishere: 寶 我失業了 05/15 16:22

→ SiranuiFlare: 來跟我一樣搬磚 05/15 16:23

推 thibw13ug1: GPT真的好強 05/15 16:23

→ OnishiSaori: 大濕 05/15 16:25

推 OREOMZA: 包養分析了解對方想法。 05/15 16:25

→ osopopototo: 測資真的挺搞的 05/15 16:30

→ oinishere: 喜訊 根本不用pq 我用普通queue 也可以 現在我700ms 05/15 16:31

推 Che31128: 賀 05/15 16:38

推 wu10200512: 別卷了 這些題目我都不會 嗚嗚哇哇哇 05/15 16:48