Create 2258.Escape-the-Spreading-Fire_v4.cpp

wisdompeak · web-flow · commit 930063ae729f · 2022-05-07T10:27:21.000-07:00
diff --git a/BFS/2258.Escape-the-Spreading-Fire/2258.Escape-the-Spreading-Fire_v4.cpp b/BFS/2258.Escape-the-Spreading-Fire/2258.Escape-the-Spreading-Fire_v4.cpp
@@ -0,0 +1,122 @@
+class Solution {
+    vector<pair<int,int>>dir = {{1,0},{-1,0},{0,1},{0,-1}};
+public:
+    int maximumMinutes(vector<vector<int>>& grid) 
+    {
+        int m = grid.size();
+        int n = grid[0].size();
+
+        vector<vector<int>>person = bfs(grid, 0);
+        vector<vector<int>>fire = bfs(grid, 1);
+        
+        if (person[m-1][n-1]==INT_MAX || person[m-1][n-1] > fire[m-1][n-1])
+            return -1;
+        if (fire[m-1][n-1]==INT_MAX)
+            return 1e9;
+
+        vector<vector<int>>visited(m, vector<int>(n));
+        priority_queue<array<int,3>>pq;
+        pq.push({fire[m-1][n-1], m-1, n-1});
+        while (!pq.empty())
+        {
+            auto [t, x, y] = pq.top();
+            pq.pop();
+            if (visited[x][y]) continue;
+            visited[x][y] = 1;
+            if (x==0 && y==0) return t;
+
+            for (auto& [dx, dy] : dir)
+            {
+                int i = x+dx, j = y+dy;
+                if (i<0||i>=m||j<0||j>=n) continue;
+                if (grid[i][j]==2) continue;
+                if (visited[i][j]) continue;                
+                pq.push({min(t-1,fire[i][j]-1), i,j});                                
+            }
+        }
+        return -1;
+    }
+
+    bool checkOK(vector<vector<int>>& grid, vector<vector<int>>fire, int D)
+    {
+        int m = grid.size();
+        int n = grid[0].size();
+        vector<vector<int>>visited(m, vector<int>(n));
+
+        queue<pair<int,int>>q;
+        q.push({0,0});
+        visited[0][0] = 1;
+        int step = D;
+        while (!q.empty())
+        {
+            int len = q.size();
+            while (len--)
+            {
+                auto [x,y] = q.front();
+                q.pop();
+                for (auto& [dx, dy] : dir)
+                {
+                    int i = x+dx, j = y+dy;
+                    if (i<0||i>=m||j<0||j>=n) continue;
+                    if (grid[i][j]==2) continue;
+                    if (visited[i][j]) continue;
+                    if ((i!=m-1 || j!=n-1) && step+1 >= fire[i][j]) continue;
+                    q.push({i,j});
+                    visited[i][j] = 1;
+                    if (i==m-1 && j==n-1 && step+1 <= fire[m-1][n-1]) return true;
+                }
+            }
+            step++;
+        }
+        return false;
+    }
+
+    vector<vector<int>>bfs(vector<vector<int>>&grid, int type)
+    {
+        int m = grid.size();
+        int n = grid[0].size();
+        vector<vector<int>>rets(m, vector<int>(n,INT_MAX));
+        queue<pair<int,int>>q;
+
+        if (type==0)        
+        {
+            q.push({0,0});
+            rets[0][0] = 0;
+        }            
+        else
+        {            
+            for (int i=0; i<m; i++)
+                for (int j=0; j<n; j++)
+                    if (grid[i][j]==1) 
+                    {
+                        q.push({i,j});
+                        rets[i][j] = 0;
+                    }                        
+        }
+        
+        int step = 0;
+        while (!q.empty())
+        {
+            int len = q.size();
+            while (len--)
+            {
+                auto [x,y] = q.front();
+                q.pop();
+
+                for (auto& [dx, dy] : dir)
+                {
+                    int i = x+dx, j = y+dy;
+                    if (i<0||i>=m||j<0||j>=n) continue;
+                    if (grid[i][j]==2) continue;
+                    if (rets[i][j]!=INT_MAX) continue;
+                    rets[i][j] = step+1;
+                    if (i!=m-1 || j!=n-1)
+                        q.push({i,j});
+                }
+            }
+            step++;
+        }
+
+        return rets;
+    }
+};
