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

看板Marginalman作者osopopototo (我是垃圾哦)時間1年前 (2024/05/15 12:55)推噓6(6推 0噓 1→)

留言7則, 7人參與討論串222/1548 (看更多)

給一個nxn的矩陣，裡面包含0和1 求從(0,0)出發到(n-1,n-1)離所有1最遠的路徑，其中與任一1最近的距離距離定義為曼哈頓距離(|x1-x2|+|y1-y2|) -- 因為不太可能每一步和所有1算距離應該要從1反推回去，得到一個nxn的距離矩陣再尋路用bfs可以直觀算出距離矩陣得到距離矩陣後，利用它尋路要尋找所有路徑中可以和1離最遠的路徑因為n到400，用dfs窮舉應該會炸掉用priority queue，用類似dij那啥東東的方法從(0,0)開始走，每次挑路徑離1最遠的cell走 priority queue儲存各自路徑離1最近的距離直到第一個走到(n-1,n-1)的即是離1最遠的路徑 -- 這題好搞一直TLE 偷看解答發現bfs方法不一樣我原本是每個1去跑一次bfs，這個bfs會終止在與(0,0)的距離(因為接下去不影響答案) 或是不用再更新為止後來學解答，應該要所有1一起當source，也是到不再更新為止，只需要跑一次 class Solution { public: std::vector<std::vector<int>> distMap; std::vector<std::vector<bool>> visited; int step[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int n; int dij(int i, int j, int id, int jd){ std::priority_queue<std::pair<int ,std::pair<int, int>>> pq; pq.push({distMap[i][j], {i, j}}); std::pair<int ,std::pair<int, int>> top; int currMin, i1, j1, i2, j2; while(!pq.empty()){ top = pq.top(); pq.pop(); currMin = top.first; i1=top.second.first; j1=top.second.second; visited[i1][j1] = true; if(i1==id && j1==jd) return currMin; for(const auto st : step){ i2 = i1 + st[0]; j2 = j1 + st[1]; if(i2<0 || i2>=n || j2<0 || j2>=n) continue; if(visited[i2][j2]) continue; pq.push({std::min(currMin, distMap[i2][j2]), {i2, j2}}); visited[i2][j2] = true; } } return -1; } void bfs(std::vector<std::vector<int>>& grid){ std::deque<std::pair<int, int>> pd; for(int i=0; i<n; ++i){ for(int j=0; j<n; ++j){ if(grid[i][j]){ distMap[i][j] = 0; pd.emplace_back(i, j); } } } int i1, j1, i2, j2; std::pair<int, int> front; while(!pd.empty()){ front = pd.front(); i1 = front.first; j1 = front.second; pd.pop_front(); for(const auto st : step){ i2 = i1+st[0]; j2 = j1+st[1]; if(i2<0 || i2>=n || j2<0 || j2>=n) continue; if(distMap[i2][j2] <= distMap[i1][j1]+1) continue; distMap[i2][j2] = distMap[i1][j1] + 1; pd.emplace_back(i2, j2); } } } int maximumSafenessFactor(vector<vector<int>>& grid) { n = grid.size(); distMap = std::vector<std::vector<int>>(n, std::vector<int>(n, INT_MAX)); visited = std::vector<std::vector<bool>>(n, std::vector<bool>(n, false)); bfs(grid); return dij(0, 0, n-1, n-1); } }; -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 45.144.227.54 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715748920.A.FA7.html

推

steven183

05/15 12:55, 1年前 , 1^F

05/15 12:55, 1^F

※ 編輯: osopopototo (45.144.227.54 臺灣), 05/15/2024 12:57:37

推

sustainer123

05/15 12:58, 1年前 , 2^F

05/15 12:58, 2^F

推

digua

05/15 13:00, 1年前 , 3^F