【動態規劃】【廣度優先】LeetCode2258:逃離火災

作者推薦

本文涉及的基礎知識點

二分查找算法合集
動態規劃
二分查找

題目

給你一個下標從 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

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/211105.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/211105.shtml
英文地址,請注明出處:http://en.pswp.cn/news/211105.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

pytorch:YOLOV1的pytorch實現

pytorch&#xff1a;YOLOV1的pytorch實現 注&#xff1a;本篇僅為學習記錄、學習筆記&#xff0c;請謹慎參考&#xff0c;如果有錯誤請評論指出。 參考&#xff1a; 動手學習深度學習pytorch版——從零開始實現YOLOv1 目標檢測模型YOLO-V1損失函數詳解 3.1 YOLO系列理論合集(Y…

Redis對象類型檢測與命令多態

一. 命令類型 Redis中操作鍵的命令可以分為兩類。 一種命令可以對任意類型的鍵執行&#xff0c;比如說DEL&#xff0c;EXPIRE&#xff0c;RENAME&#xff0c;TYPE&#xff0c;OBJECT命令等。 舉個例子&#xff1a; #字符串鍵 127.0.0.1:6379> set msg "hello world&…

第76講:MySQL數據庫中常用的命令行工具的基本使用

文章目錄 1.mysql客戶端命令工具2.mysqladmin管理數據庫的客戶端工具3.mysqlbinlog查看數據庫中的二進制日志4.mysqlshow統計數據庫中的信息5.mysqldump數據庫備份工具6.mysqllimport還原備份的數據7.source命令還原SQL類型的備份文件 MySQL數據庫提供了很多的命令行工具&#…

python 畫條形圖(柱狀圖)

目錄 前言 基礎介紹 月度開支的條形圖 前言 條形圖&#xff08;bar chart&#xff09;&#xff0c;也稱為柱狀圖&#xff0c;是一種以長方形的長度為變量的統計圖表&#xff0c;長方形的長度與它所對應的變量數值呈一定比例。 當使用 Python 畫條形圖時&#xff0c;通常會使…

python代碼:如何控制一個exe程序只能執行一次

import ctypes import sys def is_program_running(): # 創建互斥體 mutex_name "Global\\MonitorClientMutex" h_mutex ctypes.windll.kernel32.CreateMutexW(None, False, mutex_name) # 檢查互斥體是否已經存在 if ctypes.windll.kernel32.Get…

Centos7.9安裝谷歌【解決依賴問題】

安裝過程 mkdir /home/app cd /home/app wget https://dl.google.com/linux/direct/google-chrome-stable_current_x86_64.rpmyum install -y redhat-lsb-core-4.0-7.el6.centos.x86_64 yum install -y libX11-devel --nogpg yum install -y cmake gcc gcc-c gtk-devel gim…

vscode 編譯運行c++ 記錄

一、打開文件夾&#xff0c;新建或打開一個cpp文件 二、ctrl shift p 進入 c/c配置 進行 IntelliSense 配置。主要是選擇編譯器、 c標準&#xff0c; 設置頭文件路徑等&#xff0c;配置好后會生成 c_cpp_properties.json&#xff1b; 二、編譯運行&#xff1a; 1、選中ma…

zabbix 通過 odbc 監控 mssql

1、環境 操作系統&#xff1a;龍蜥os 8.0 zabbix&#xff1a;6.0 mssql&#xff1a;2012 2、安裝odbc 注意&#xff1a;需要在zabbix server 或者 zabbix proxy 安裝 odbc驅動程序 dnf -y install unixODBC unixODBC-devel3、安裝mssql驅動程序 注意&#xff1a;我最開始嘗試…

Tomcat管理功能使用

前言 Tomcat管理功能用于對Tomcat自身以及部署在Tomcat上的應用進行管理的web應用。在默認情況下是處于禁用狀態的。如果需要開啟這個功能&#xff0c;需要配置管理用戶&#xff0c;即配置tomcat-users.xml文件。 &#xff01;&#xff01;&#xff01;注意&#xff1a;測試功…

react 學習筆記 李立超老師 | (學習中~)

文章目錄 react學習筆記01入門概述React 基礎案例HelloWorld三個API介紹 JSXJSX 解構數組 創建react項目(手動)創建React項目(自動) | create-react-app事件處理React中的CSS樣式內聯樣式 | 內聯樣式中使用state (不建議使用)外部樣式表 | CSS Module React組件函數式組件和類組…

【數據結構和算法】反轉字符串中的單詞

其他系列文章導航 Java基礎合集數據結構與算法合集 設計模式合集 多線程合集 分布式合集 ES合集 文章目錄 其他系列文章導航 文章目錄 前言 一、題目描述 二、題解 2.1 方法一&#xff1a;雙指針 2.2 方法二&#xff1a;分割 倒序 三、代碼 3.1 方法一&#xff1a;雙…

不同品牌的手機如何投屏到蘋果MacBook?例如小米、華為怎樣投屏比較好?

習慣使用apple全家桶的人當然知道蘋果手機或iPad可以直接用airplay投屏到MacBook。 但工作和生活的多個場合里&#xff0c;并不是所有人都喜歡用同一品牌的設備&#xff0c;如果同事或同學其他品牌的手機需要投屏到MacBook&#xff0c;有什么方法可以快捷實現&#xff1f; 首先…

1 億個數據取出最大前 100 個有什么方法?

1 億個數據取出最大前 100 個有什么方法&#xff1f; 大家好&#xff0c;這是一道經常在面試中被遇到的一個問題&#xff0c;我之前面試也是被問到過得&#xff0c;現在一起學習下&#xff0c;下次再被問到就可以輕松地用對。 在計算機科學和數據處理領域&#xff0c;我們經常…

【GDB】

GDB 1. GDB調試器1.1 前言1.2 GDB編譯程序1.3 啟動GDB1.4 載入被調試程序1.5 查看源碼1.6 運行程序1.7 斷點設置1.7.1 通過行號設置斷點1.7.2 通過函數名設置斷點1.7.3 通過條件設置斷點1.7.4 查看斷點信息1.7.5 刪除斷點 1.8 單步調試1.9 2. GDB調試core文件2.1 設定core文件的…

(五)五種最新算法(SWO、COA、LSO、GRO、LO)求解無人機路徑規劃MATLAB

一、五種算法&#xff08;SWO、COA、LSO、GRO、LO&#xff09;簡介 1、蜘蛛蜂優化算法SWO 蜘蛛蜂優化算法&#xff08;Spider wasp optimizer&#xff0c;SWO&#xff09;由Mohamed Abdel-Basset等人于2023年提出&#xff0c;該算法模型雌性蜘蛛蜂的狩獵、筑巢和交配行為&…

iOS(swiftui)——系統懸浮窗( 可在其他應用上顯示,可實時更新內容)

因為ios系統對權限的限制是比較嚴格的,ios系統本身是不支持全局懸浮窗(可在其他app上顯示)。在iphone14及之后的iPhone機型中提供了一個叫 靈動島的功能,可以在手機上方可以添加一個懸浮窗顯示內容并實時更新,但這個功能有很多局限性 如:需要iPhone14及之后的機型且系統…

Java面試遇到的一些常見題

目錄 1. Java語言有幾種基本類型&#xff0c;分別是什么&#xff1f; 整數類型&#xff08;Integer Types&#xff09;&#xff1a; 浮點類型&#xff08;Floating-Point Types&#xff09;&#xff1a; 字符類型&#xff08;Character Type&#xff09;&#xff1a; 布爾類…

(六)五種最新算法(SWO、COA、LSO、GRO、LO)求解無人機路徑規劃MATLAB

一、五種算法&#xff08;SWO、COA、LSO、GRO、LO&#xff09;簡介 1、蜘蛛蜂優化算法SWO 蜘蛛蜂優化算法&#xff08;Spider wasp optimizer&#xff0c;SWO&#xff09;由Mohamed Abdel-Basset等人于2023年提出&#xff0c;該算法模型雌性蜘蛛蜂的狩獵、筑巢和交配行為&…

【完整項目】雙模式答題卡識別軟件中YOLO模式的訓練部分詳解,包括訓練填涂區域和手寫準考證號,手把手詳細教學,可延申拓展訓練其他圖像數據

目錄 前言1. 數據準備2. 數據標注3. 先跑起來Windows下用本地的CPU或GPU訓練本地Windows系統連接服務器訓練前言 前文:【完整項目】基于Python+Tkinter+OpenCV+Yolo+手寫OCR的雙模式答題卡識別軟件的設計與實現 如果你需要訓練自己的答題卡模型,那么請先看上面的文章鏈接。…

Flutter自定義下拉選擇框dropDownMenu

利用PopupMenuButton和PopupMenuItem寫了個下拉選擇框&#xff0c;之所以不采用系統的&#xff0c;是因為自定義的更能適配項目需求&#xff0c;話不多說&#xff0c;直接看效果 下面直接貼出代碼、代碼中注釋寫的都很清楚&#xff0c;使用起來應該很方便&#xff0c;如果有任何…