當前位置：首頁 > news >正文

國外有哪些網站做推廣的比較好黃頁88網站推廣方案

news 2025/7/14 19:16:17

國外有哪些網站做推廣的比較好,黃頁88網站推廣方案,論壇開源網站源碼,如何做網站公證本文涉及知識點 CBFS算法 C二分查找 LeetCode2812. 找出最安全路徑給你一個下標從 0 開始、大小為 n x n 的二維矩陣 grid ，其中 (r, c) 表示： 如果 grid[r][c] 1 ，則表示一個存在小偷的單元格如果 grid[r][c] 0 ，則表示一…

本文涉及知識點

C++BFS算法
C++二分查找

LeetCode2812. 找出最安全路徑

給你一個下標從 0 開始、大小為 n x n 的二維矩陣 grid ，其中 (r, c) 表示：
如果 grid[r][c] = 1 ，則表示一個存在小偷的單元格
如果 grid[r][c] = 0 ，則表示一個空單元格
你最開始位于單元格 (0, 0) 。在一步移動中，你可以移動到矩陣中的任一相鄰單元格，包括存在小偷的單元格。
矩陣中路徑的安全系數定義為：從路徑中任一單元格到矩陣中任一小偷所在單元格的最小曼哈頓距離。
返回所有通向單元格 (n - 1, n - 1) 的路徑中的最大安全系數。
單元格 (r, c) 的某個相鄰單元格，是指在矩陣中存在的 (r, c + 1)、(r, c - 1)、(r + 1, c) 和 (r - 1, c) 之一。
兩個單元格 (a, b) 和 (x, y) 之間的曼哈頓距離等于 | a - x | + | b - y | ，其中 |val| 表示 val 的絕對值。
示例 1：
在這里插入圖片描述

輸入：grid = [[1,0,0],[0,0,0],[0,0,1]]
輸出：0
解釋：從 (0, 0) 到 (n - 1, n - 1) 的每條路徑都經過存在小偷的單元格 (0, 0) 和 (n - 1, n - 1) 。
示例 2：
在這里插入圖片描述

輸入：grid = [[0,0,1],[0,0,0],[0,0,0]]
輸出：2
解釋：
上圖所示路徑的安全系數為 2：

該路徑上距離小偷所在單元格（0，2）最近的單元格是（0，0）。它們之間的曼哈頓距離為 | 0 - 0 | + | 0 - 2 | = 2 。
可以證明，不存在安全系數更高的其他路徑。
示例 3：

輸入：grid = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
輸出：2
解釋：
上圖所示路徑的安全系數為 2：

該路徑上距離小偷所在單元格（0，3）最近的單元格是（1，2）。它們之間的曼哈頓距離為 | 0 - 1 | + | 3 - 2 | = 2 。
該路徑上距離小偷所在單元格（3，0）最近的單元格是（3，2）。它們之間的曼哈頓距離為 | 3 - 3 | + | 0 - 2 | = 2 。
可以證明，不存在安全系數更高的其他路徑。

提示：
1 <= grid.length == n <= 400
grid[i].length == n
grid[i][j] 為 0 或 1
grid 至少存在一個小偷

二分查找

一，BFS出各單格距離小偷的位置（層次）leve。
二，二分查找。Check(mid) 是否存在安全系數為mid或更大的路徑。隨著mid從0到leve[0][0]，Check的返回值逐步由true，變成false。我們尋找最后一個true。Check函數的大致步驟：
a,連通距離小偷大于等與mid的單格。
b，看右下角的層次是否大于等于0。

代碼

第一版（超時）

class CGrid {
public:CGrid(int rCount, int cCount) :m_r(rCount), m_c(cCount) {}vector<vector<pair<int, int>>> NeiBo(std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, int iConnect = 4){vector<vector<pair<int, int>>> vNeiBo(m_r * m_c);auto Move = [&](int preR, int preC, int r, int c){if ((r < 0) || (r >= m_r)){return;}if ((c < 0) || (c >= m_c)){return;}if (funVilidCur(preR, preC) && funVilidNext(r, c)){vNeiBo[Mask(preR, preC)].emplace_back(r, c);}};for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){for (int k = 0; k < iConnect; k++){Move(r, c, r + s_Moves[k][0], c + s_Moves[k][1]);}}}return vNeiBo;}void EnumGrid(std::function<void(int, int)> call){for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){call(r, c);}}}	vector<pair<int, int>> GetPos(std::function<bool(int, int)> fun) {vector<pair<int, int>> ret;for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){if (fun(r, c)) {ret.emplace_back(r, c);}}}return ret;}inline int Mask(int r, int c) { return  m_c * r + c; }const int m_r, m_c;const inline static int s_Moves[][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
};class CBFSLeve {
public :static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {vector<int> leves(neiBo.size(), -1);for (const auto& s : start) {leves[s] = 0;}for (int i = 0; i < start.size(); i++) {for (const auto& next : neiBo[start[i]]) {if (-1 != leves[next]) { continue; }leves[next] = leves[start[i]]+1;start.emplace_back(next);}}return leves;}static vector<vector<int>> Leve(CGrid& grid, vector<pair<int, int>> start, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, int iConnect = 4 ) {auto neiBo = grid.NeiBo(funVilidCur, funVilidCur, iConnect);vector<vector<int>> leves(grid.m_r, vector<int>(grid.m_c, -1));for (const auto& [r,c] : start) {leves[r][c] = 0;}for (int i = 0; i < start.size(); i++) {const int iMask = grid.Mask(start[i].first, start[i].second);for (const auto& [r1,c1] : neiBo[iMask]) {if (-1 != leves[r1][c1]) { continue; }leves[r1][c1] = leves[start[i].first][start[i].second] + 1;start.emplace_back(r1,c1);}}return leves;}
};template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist( _Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd( _Pr pr){int leftInclude = m_iMin;int right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {public:int maximumSafenessFactor(vector<vector<int>>& grid) {CGrid ng(grid.size(),grid[0].size());auto start = ng.GetPos([&](int r, int c) {return grid[r][c] == 1; });auto vilid = [&](int r, int c) {return true; };auto leve = CBFSLeve::Leve(ng, start,vilid, vilid);auto Check = [&](int mid) {auto vilid1 = [&](int r, int c) {return leve[r][c] >= mid; };auto leve1 = CBFSLeve::Leve(ng, { {0,0 } }, vilid1, vilid1);return leve1.back().back() >= 0;};CBinarySearch<int> bs(0, leve[0][0]);return bs.FindEnd(Check);}};

第二版

中間過程，求臨接表浪費很多時間，省略后，速度提高幾倍。就可以過了。許多單格和起點不連通，無需計算。

class CGrid {
public:CGrid(int rCount, int cCount) :m_r(rCount), m_c(cCount) {}template<class Fun1,class Fun2>vector<vector<pair<int, int>>> NeiBo(Fun1 funVilidCur, Fun2 funVilidNext, int iConnect = 4){vector<vector<pair<int, int>>> vNeiBo(m_r * m_c);for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){if (!funVilidCur(r, c))continue;auto& v = vNeiBo[Mask(r, c)];if ((r > 0)&& funVilidNext(r-1, c)) {v.emplace_back(r-1, c);}if ((c > 0) && funVilidNext(r , c - 1)) {v.emplace_back(r, c - 1);}if ((r+1 < m_r ) && funVilidNext(r + 1, c)) {v.emplace_back(r + 1, c);}if ((c+1 <m_c ) && funVilidNext(r, c + 1)) {v.emplace_back(r, c + 1);}}}return vNeiBo;}void EnumGrid(std::function<void(int, int)> call){for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){call(r, c);}}}	vector<pair<int, int>> GetPos(std::function<bool(int, int)> fun) {vector<pair<int, int>> ret;for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){if (fun(r, c)) {ret.emplace_back(r, c);}}}return ret;}inline int Mask(int r, int c) { return  m_c * r + c; }const int m_r, m_c;const inline static int s_Moves[][2] = { {1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1} };
};class CBFSLeve {
public :static vector<int> Leve(const vector<vector<int>>& neiBo, vector<int> start) {vector<int> leves(neiBo.size(), -1);for (const auto& s : start) {leves[s] = 0;}for (int i = 0; i < start.size(); i++) {for (const auto& next : neiBo[start[i]]) {if (-1 != leves[next]) { continue; }leves[next] = leves[start[i]]+1;start.emplace_back(next);}}return leves;}static vector<vector<int>> Dis(CGrid& grid, vector<pair<int, int>> start, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext, const int& iConnect = 4 ) {static short dir[8][2] = { {0, 1}, {1, 0}, {-1, 0},{ 0, -1},{1,1},{1,-1},{-1,1},{-1,-1} };vector<vector<int>> vDis(grid.m_r, vector<int>(grid.m_c, -1));for (const auto& [r,c] : start) {vDis[r][c] = 0;}for (int i = 0; i < start.size(); i++) {const auto [r,c] = start[i];if (!funVilidCur(r, c)) { continue; }for (int k = 0; k < iConnect; k++) {const int r1 = r + dir[k][0];const int c1 = c + dir[k][1];if ((r1 < 0) || (r1 >= grid.m_r) || (c1 < 0) || (c1 >= grid.m_c)) { continue; }if (funVilidNext(r1, c1)&&(-1 == vDis[r1][c1])) {start.emplace_back(r1, c1);vDis[r1][c1]= vDis[r][c] + 1;}}}return vDis;}
};template<class INDEX_TYPE>
class CBinarySearch
{
public:CBinarySearch(INDEX_TYPE iMinIndex, INDEX_TYPE iMaxIndex):m_iMin(iMinIndex),m_iMax(iMaxIndex) {}template<class _Pr>INDEX_TYPE FindFrist( _Pr pr){auto left = m_iMin - 1;auto rightInclue = m_iMax;while (rightInclue - left > 1){const auto mid = left + (rightInclue - left) / 2;if (pr(mid)){rightInclue = mid;}else{left = mid;}}return rightInclue;}template<class _Pr>INDEX_TYPE FindEnd( _Pr pr){int leftInclude = m_iMin;int right = m_iMax + 1;while (right - leftInclude > 1){const auto mid = leftInclude + (right - leftInclude) / 2;if (pr(mid)){leftInclude = mid;}else{right = mid;}}return leftInclude;}
protected:const INDEX_TYPE m_iMin, m_iMax;
};class Solution {public:int maximumSafenessFactor(vector<vector<int>>& grid) {CGrid ng(grid.size(),grid[0].size());		auto start = ng.GetPos([&](int r, int c) {return grid[r][c] == 1; });auto vilid = [&](int r, int c) {return true; };auto dis = CBFSLeve::Dis(ng, start,vilid, vilid);auto Check = [&](int mid) {auto vilid1 = [&](int r, int c) {return dis[r][c] >= mid; };auto dis2 = CBFSLeve::Dis(ng, { {0,0} }, vilid1, vilid1);return dis2.back().back() >= 0;};CBinarySearch<int> bs(0, min(dis[0][0],dis.back().back()));return bs.FindEnd(Check);}};

單元測試

vector<vector<int>> grid;TEST_METHOD(TestMethod1){grid = { {1} };auto res = Solution().maximumSafenessFactor(grid);AssertEx(0, res);}TEST_METHOD(TestMethod15){grid = { {1,0,0},{0,0,0},{0,0,1} };auto res = Solution().maximumSafenessFactor(grid);AssertEx(0, res);}TEST_METHOD(TestMethod16){grid = { {0,0,1},{0,0,0},{0,0,0} };auto res = Solution().maximumSafenessFactor(grid);AssertEx(2, res);}TEST_METHOD(TestMethod17){grid = { {0,0,0,1},{0,0,0,0},{0,0,0,0},{1,0,0,0} };auto res = Solution().maximumSafenessFactor(grid);AssertEx(2, res);}TEST_METHOD(TestMethod18){grid.assign(400, vector<int>(400));grid[0][0] = 1;auto res = Solution().maximumSafenessFactor(grid);AssertEx(0, res);}TEST_METHOD(TestMethod19){grid.assign(400, vector<int>(400));grid.back().back() = 1;auto res = Solution().maximumSafenessFactor(grid);AssertEx(0, res);}TEST_METHOD(TestMethod20){grid.assign(400, vector<int>(400));grid[0].back() = 1;auto res = Solution().maximumSafenessFactor(grid);AssertEx(399, res);}TEST_METHOD(TestMethod21){grid.assign(400, vector<int>(400));grid.back()[0] = 1;auto res = Solution().maximumSafenessFactor(grid);AssertEx(399, res);}

擴展閱讀

我想對大家說的話
工作中遇到的問題，可以按類別查閱鄙人的算法文章，請點擊《算法與數據匯總》。
學習算法：按章節(jié)學習《喜缺全書算法冊》，大量的題目和測試用例，打包下載。重視操作
有效學習：明確的目標及時的反饋拉伸區(qū)（難度合適）專注
聞缺陷則喜(喜缺)是一個美好的愿望，早發(fā)現問題，早修改問題，給老板節(jié)約錢。
子墨子言之：事無終始，無務多業(yè)。也就是我們常說的專業(yè)的人做專業(yè)的事。
如果程序是一條龍，那算法就是他的是睛
失敗+反思=成功成功+反思=成功

視頻課程

先學簡單的課程，請移步CSDN學院，聽白銀講師（也就是鄙人）的講解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成戰(zhàn)斗了，為老板分憂，請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176