作者推薦
本文涉及的基礎知識點
二分查找算法合集
動態規劃
二分查找
題目
給你一個下標從 0 開始大小為 m x n 的二維整數數組 grid ,它表示一個網格圖。每個格子為下面 3 個值之一:
0 表示草地。
1 表示著火的格子。
2 表示一座墻,你跟火都不能通過這個格子。
一開始你在最左上角的格子 (0, 0) ,你想要到達最右下角的安全屋格子 (m - 1, n - 1) 。每一分鐘,你可以移動到 相鄰 的草地格子。每次你移動 之后 ,著火的格子會擴散到所有不是墻的 相鄰 格子。
請你返回你在初始位置可以停留的 最多 分鐘數,且停留完這段時間后你還能安全到達安全屋。如果無法實現,請你返回 -1 。如果不管你在初始位置停留多久,你 總是 能到達安全屋,請你返回 109。
注意,如果你到達安全屋后,火馬上到了安全屋,這視為你能夠安全到達安全屋。
如果兩個格子有共同邊,那么它們為 相鄰 格子。
示例 1:
輸入:grid = [[0,2,0,0,0,0,0],[0,0,0,2,2,1,0],[0,2,0,0,1,2,0],[0,0,2,2,2,0,2],[0,0,0,0,0,0,0]]
輸出:3
解釋:上圖展示了你在初始位置停留 3 分鐘后的情形。
你仍然可以安全到達安全屋。
停留超過 3 分鐘會讓你無法安全到達安全屋。
示例 2:
輸入:grid = [[0,0,0,0],[0,1,2,0],[0,2,0,0]]
輸出:-1
解釋:上圖展示了你馬上開始朝安全屋移動的情形。
火會蔓延到你可以移動的所有格子,所以無法安全到達安全屋。
所以返回 -1 。
示例 3:
輸入:grid = [[0,0,0],[2,2,0],[1,2,0]]
輸出:1000000000
解釋:上圖展示了初始網格圖。
注意,由于火被墻圍了起來,所以無論如何你都能安全到達安全屋。
所以返回 109。
提示:
m == grid.length
n == grid[i].length
2 <= m, n <= 300
4 <= m * n <= 2 * 104
grid[i][j] 是 0 ,1 或者 2 。
grid[0][0] == grid[m - 1][n - 1] == 0
分析
動態規劃
時間復雜度: O(n)。BFS時間復雜度O(n),計算最晚時間O(1)。
我么把每個單格看成一個圖論的一個節點,那么二維動態規劃就變成了一維動態規劃。我們通過廣度優先可以計算出人和火到達各點時間,如果無法到達,記做109的時間達到,單格數不超過104,所以不可能這么晚到達的。
原理
安全屋 | 人必須比火早到或同時到達 |
非安全屋 | 人必須比火早到 |
令安全屋上面或左面的格子為終點。能從通過某個終點到達安全屋的充分必要條件是:
一,比火早到終點。
二,人到達終點時,火沒到安全屋。
只需要考慮終點格子,不需要考慮中間格子。如果中間某個格子火追上人,則終點格子火一定能追上人。火跟著人走。
大致模塊和步驟
一,封裝單源BFS和多源BFS。
二,初始鄰接表和初始著火點。
三,計算人和火到達各點時間。
四,計算最晚出發時間。
特殊情況分析
人無法到達終點 | fireEnd<=peoEnd,過 fireEnd-peoEnd-1 為負數 peoStart為負數 | |
人能到達終點 | 火無法到達終點、完全屋 | fireEnd為10^9 peoEnd小于mn 故 fireEnd-peoEnd-1 遠大于mn |
人能到達終點 | 火無法到達終點、能到完全屋 | 結果正確 計算的結果是:比火到安全屋提前一天到終點,實際結果也是。 |
代碼
核心代碼
class Solution {
public:int maximumMinutes(vector<vector<int>>& grid) {m_r = grid.size();m_c = grid.front().size();vector<vector<int>> vNeiB(m_r*m_c);auto Add =[&](const auto & n1, const auto & n2){vNeiB[n1].emplace_back(n2);vNeiB[n2].emplace_back(n1);};vector<int> vFire;for (int r = 0; r < m_r; r++){for (int c = 0; c < m_c; c++){if (2 == grid[r][c]){continue;}const int mask = m_c * r + c;if (1 == grid[r][c]){vFire.emplace_back(mask);} if (r && (2 != grid[r-1][c])){Add(mask, mask - m_c);}if( c && ( 2 != grid[r][c-1])){Add(mask, mask - 1);}}}CBFSDis disPeo(vNeiB, vector<int>{0});CBFSDis disFire(vNeiB, vFire);const int fireEnd1 = min(disFire.m_vDis[m_r * m_c - 1 - m_c], disFire.m_vDis.back());const int fireEnd2 = min(disFire.m_vDis[m_r * m_c - 1 - 1], disFire.m_vDis.back());const int peoStart1 = fireEnd1 - disPeo.m_vDis[m_r * m_c - 1 - m_c] - 1;const int peoStart2 = fireEnd2 - disPeo.m_vDis[m_r * m_c - 1 - 1] - 1;const int iRet = max(peoStart1, peoStart2);if (iRet < 0){return -1;}if (iRet > m_r * m_c){return 1e9;}return iRet;}int m_r,m_c;
};
測試用例
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<vector<int>> grid;long long budget;{Solution slu; grid = { {0,2,0,0,0,0,0},{0,0,0,2,2,1,0},{0,2,0,0,1,2,0},{0,0,2,2,2,0,2},{0,0,0,0,0,0,0} };auto res = slu.maximumMinutes(grid);Assert(3, res);}{Solution slu;grid = { {0,0,0,0},{0,1,2,0},{0,2,0,0} };auto res = slu.maximumMinutes(grid);Assert(-1, res);}{Solution slu;grid = { {0,0,0},{2,2,0},{1,2,0} };auto res = slu.maximumMinutes(grid);Assert(1000000000, res);}{Solution slu;grid = { {0,2,0,0,1},{0,2,0,2,2},{0,2,0,0,0},{0,0,2,2,0},{0,0,0,0,0} };auto res = slu.maximumMinutes(grid);Assert(0, res);}{Solution slu;grid = { {0,0,0,0,0,0},{0,2,2,2,2,0},{0,0,0,1,2,0},{0,2,2,2,2,0},{0,0,0,0,0,0} };auto res = slu.maximumMinutes(grid);Assert(1, res);}//CConsole::Out(res);
}
2023年3月舊代碼:二分查找實現
如果t1 <t2,t2能到達安全屋,則t1一定可能。我們尋找能達到的最大t,左閉右開空間。
class Solution {
public:
int maximumMinutes(vector<vector>& grid) {
m_r = grid.size();
m_c = grid[0].size();
InitNotCanVisit(grid);
if (!bfs(0, grid))
{
return -1;
}
if (bfs(30*1000, grid))
{
return 1000 * 1000 * 1000;
}
int left = 0, right = 30 * 1000;
while (right > left + 1)
{
const int iMid = left + (right - left) / 2;
if (bfs(iMid, grid))
{
left = iMid;
}
else
{
right = iMid;
}
}
return left;
}
void InitNotCanVisit(const vector<vector>& grid)
{
m_vNotCanVisit.assign(m_r, vector(m_c, m_iNotMay));
std::queue<std::pair<int, int>> preFire;
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
if (0 != grid[r][c])
{
m_vNotCanVisit[r][c] = 0;
}
if (1 == grid[r][c])
{
preFire.emplace(r, c);
}
}
}
for (int iStep = 0; preFire.size(); iStep++)
{
std::queue<std::pair<int, int>> curFire;
while (preFire.size())
{
const int r = preFire.front().first;
const int c = preFire.front().second;
preFire.pop();
Fire(curFire, r + 1, c, grid,iStep);
Fire(curFire, r - 1, c, grid, iStep);
Fire(curFire, r, c + 1, grid, iStep);
Fire(curFire, r, c - 1, grid, iStep);
}
preFire.swap(curFire);
}
m_vNotCanVisit.back().back()++;
}
void Fire(std::queue<std::pair<int, int>>& curFire, int r, int c, const vector<vector>& grid,const int iStep)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (m_iNotMay != m_vNotCanVisit[r][c])
{
return;
}
m_vNotCanVisit[r][c] = iStep;
curFire.emplace(r, c);
}
bool bfs(int iStep, const vector<vector>& grid)
{
std::queue<std::pair<int, int>> prePeo;
vector<vector> vHasDo(m_r, vector(m_c));
prePeo.emplace(0, 0);
for (; prePeo.size(); iStep++)
{
std::queue<std::pair<int, int>> curPeo;
while (prePeo.size())
{
const int r = prePeo.front().first;
const int c = prePeo.front().second;
if ((m_r - 1 == r) && (m_c - 1 == c))
{
return true;
}
prePeo.pop();
MovePeo(vHasDo, curPeo, r+1, c, grid, iStep);
MovePeo(vHasDo, curPeo, r - 1, c, grid, iStep);
MovePeo(vHasDo, curPeo, r, c + 1, grid, iStep);
MovePeo(vHasDo, curPeo, r, c - 1, grid, iStep);
}
prePeo.swap(curPeo);
}
return false;
}
void MovePeo(vector<vector>& vHasDo,std::queue<std::pair<int, int>>& curPeo, int r, int c, const vector<vector>& grid, const int iStep)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (iStep >= m_vNotCanVisit[r][c])
{
return;
}
if (vHasDo[r][c])
{
return;
}
vHasDo[r][c] = true;
curPeo.emplace(r, c);
}
int m_r;
int m_c;
const int m_iNotMay = 1000 * 100;
vector<vector> m_vNotCanVisit;
};
2023年9月舊代碼
class CBFSGridDist
{
public:
CBFSGridDist(int r, int c) :m_r?, m_c?,m_vDis(r, vector(c, -1)), m_bCanVisit(r,vector(c,true))
{
}
void BFS()
{
while (m_que.size())
{
const auto [r, c] = m_que.front();
m_que.pop();
const int iDis = m_vDis[r][c] + 1;
Move(r,c,r + 1, c, iDis);
Move(r, c, r - 1, c, iDis);
Move(r, c, r, c + 1, iDis);
Move(r, c, r, c - 1, iDis);
};
}
void AddDist(int r, int c, int iDis)
{
m_vDis[r][c] = iDis;
m_que.emplace(r, c);
}
protected:
void Move (int preR, int preC, int r, int c, int iDis)
{
if ((r < 0) || (r >= m_r))
{
return;
}
if ((c < 0) || (c >= m_c))
{
return;
}
if (-1 != m_vDis[r][c]) {
return;
}
if (!m_bCanVisit[r][c])
{
return;
}
AddDist(r, c, iDis);
};
queue<pair<int, int>> m_que;
public:
vector<vector> m_bCanVisit;
vector<vector> m_vDis;
const int m_r, m_c;
};
class Solution {
public:
int maximumMinutes(vector<vector>& grid) {
m_r = grid.size();
m_c = grid.front().size();
CBFSGridDist bfsPeo(m_r, m_c), bfsFire(m_r, m_c);
for (int r = 0; r < m_r; r++)
{
for (int c = 0; c < m_c; c++)
{
if (2 == grid[r][c])
{
bfsFire.m_bCanVisit[r][c] = false;
bfsPeo.m_bCanVisit[r][c] = false;
}
if (1 == grid[r][c])
{
bfsFire.AddDist(r, c, 0);
}
}
}
bfsPeo.AddDist(0, 0, 0);
bfsFire.BFS();
bfsPeo.BFS();
const int iPeo = bfsPeo.m_vDis.back().back();
if (-1 == iPeo)
{//人無法到達
return -1;
}
const int iFire = bfsFire.m_vDis.back().back();
if (-1 == iFire)
{//火無法到達
return 1000 * 1000 * 1000;
}
if (iPeo > iFire)
{//火比人先到
return -1;
}
const int p1 = bfsPeo.m_vDis[m_r - 2].back();
const int p2 = bfsPeo.m_vDis.back()[m_c - 2];
const int f1 = bfsFire.m_vDis[m_r - 2].back();
const int f2 = bfsFire.m_vDis.back()[m_c - 2];
int iRet = -1;
if ( p1 > 0)
{//人通過上面進入完全屋
const int cur = min(f1<0?1e9:f1, (f2<0?1e9:f2) + 1) - (p1 + 1);
iRet = max(iRet, cur);
}
if (p2 > 0)
{//人通過左邊進入安全屋
const int cur = min((f1 < 0 ? 1e9 : f1) +1, (f2 < 0 ? 1e9 : f2)) - (p2+1);
iRet = max(iRet, cur);
}
return iRet;
}
int m_r, m_c;
};
擴展閱讀
視頻課程
有效學習:明確的目標 及時的反饋 拉伸區(難度合適),可以先學簡單的課程,請移步CSDN學院,聽白銀講師(也就是鄙人)的講解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成戰斗了,為老板分憂,請學習C#入職培訓、C++入職培訓等課程
https://edu.csdn.net/lecturer/6176
相關下載
想高屋建瓴的學習算法,請下載《喜缺全書算法冊》doc版
https://download.csdn.net/download/he_zhidan/88348653
我想對大家說的話 |
---|
聞缺陷則喜是一個美好的愿望,早發現問題,早修改問題,給老板節約錢。 |
子墨子言之:事無終始,無務多業 |
。也就是我們常說的專業的人做專業的事。 |
|如果程序是一條龍,那算法就是他的是睛|
測試環境
操作系統:win7 開發環境: VS2019 C++17
或者 操作系統:win10 開發環境:
VS2022 C++17