【动态规划】【广度优先】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 public: int maximumMinutes(vector m_r = grid.size(); m_c = grid.front().size(); vector vNeiB[n1].emplace_back(n2); vNeiB[n2].emplace_back(n1); }; vector for (int c = 0; 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 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 = m_r))

{

return;

}

if ((c = m_c))

{

return;

}

if (-1 != m_vDis[r][c]) {

return;

}

if (!m_bCanVisit[r][c])

{

return;

}

AddDist(r, c, iDis);

};

queue m_que;

public:

vector m_bCanVisit;

vector m_vDis;

const int m_r, m_c;

};

class Solution {

public:

int maximumMinutes(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

{

for (int c = 0; 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