給一個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-website.tw), 來自: 45.144.227.54 (臺灣) ※ 文章網址: https://ptt-website.tw/Marginalman/M.1715748920.A.FA7

推 steven183: 別卷了 05/15 12:55

推 sustainer123: 大師 05/15 12:58

推 digua: 大獅 05/15 13:00

推 DJYOSHITAKA: 你也是刷題大師 05/15 13:07

推 mushrimp5466: 太師 05/15 13:15

推 peernut: 包養分析注意對方言行。 05/15 13:15