Solution

Method 1 – BFS with Flood Simulation

Intuition

We need to reach the destination before the flood blocks the path. By precomputing the time each cell gets flooded (using BFS from all flood sources), we can then use another BFS to find the shortest path from S to D, only stepping into cells before they flood.

Approach

Use BFS to compute the earliest time each cell becomes flooded.
Use BFS from S to D, only moving to cells that are not stone and not flooded at the current or next time.
Track visited cells with the time to avoid revisiting with worse timing.
Return the minimum time to reach D, or -1 if impossible.

Code

[{"language":"C++","code":"#include <queue>\nclass Solution {\npublic:\n    int minTimeToDestination(vector<vector<char>>& land) {\n        int n = land.size(), m = land[0].size();\n        vector<vector<int>> flood(n, vector<int>(m, INT_MAX));\n        queue<pair<int,int>> q;\n        int sx, sy, dx, dy;\n        for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {\n            if (land[i][j] == '*') { flood[i][j] = 0; q.push({i,j}); }\n            if (land[i][j] == 'S') { sx = i; sy = j; }\n            if (land[i][j] == 'D') { dx = i; dy = j; }\n        }\n        int dirs[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};\n        // Flood BFS\n        while (!q.empty()) {\n            auto [x,y] = q.front(); q.pop();\n            for (auto& d : dirs) {\n                int nx = x+d[0], ny = y+d[1];\n                if (nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]=='.'&&flood[nx][ny]>flood[x][y]+1) {\n                    flood[nx][ny]=flood[x][y]+1; q.push({nx,ny});\n                }\n            }\n        }\n        // BFS from S\n        queue<tuple<int,int,int>> q2; q2.push({sx,sy,0});\n        vector<vector<int>> vis(n, vector<int>(m, INT_MAX)); vis[sx][sy]=0;\n        while (!q2.empty()) {\n            auto [x,y,t]=q2.front(); q2.pop();\n            if (x==dx&&y==dy) return t;\n            for (auto& d : dirs) {\n                int nx=x+d[0], ny=y+d[1], nt=t+1;\n                if (nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]!='X'&&nt<flood[nx][ny]&&nt<vis[nx][ny]) {\n                    vis[nx][ny]=nt; q2.push({nx,ny,nt});\n                }\n            }\n        }\n        return -1;\n    }\n};","lang":"cpp"},{"language":"Go","code":"func minTimeToDestination(land [][]byte) int {\n    n, m := len(land), len(land[0])\n    flood := make([][]int, n)\n    for i := range flood { flood[i] = make([]int, m); for j := range flood[i] { flood[i][j]=1<<30 } }\n    var sx, sy, dx, dy int\n    q := [][2]int{}\n    for i := 0; i < n; i++ { for j := 0; j < m; j++ {\n        if land[i][j]=='*' { flood[i][j]=0; q=append(q,[2]int{i,j}) }\n        if land[i][j]=='S' { sx=i; sy=j }\n        if land[i][j]=='D' { dx=i; dy=j }\n    }}\n    dirs := [][2]int{{0,1},{1,0},{0,-1},{-1,0}}\n    for h:=0; h<len(q); h++ {\n        x,y := q[h][0],q[h][1]\n        for _,d := range dirs {\n            nx,ny := x+d[0],y+d[1]\n            if nx>=0&&nx<n&&ny>=0&&ny<m&&land[nx][ny]=='.'&&flood[nx][ny]>flood[x][y]+1 {\n                flood[nx][ny]=flood[x][y]+1; q=append(q,[2]int{nx,ny})\n            }\n        }\n    }\n    vis := make([][]int, n)\n    for i := range vis { vis[i]=make([]int,m); for j:=range vis[i]{vis[i][j]=1<<30} }\n    q2 := [][3]int{{sx,sy,0}}\n    vis[sx][sy]=0\n    for h:=0; h<len(q2); h++ {\n        x,y,t := q2[h][0],q2[h][1],q2[h][2]\n        if x==dx&&y==dy { return t }\n        for _,d := range dirs {\n            nx,ny,nt := x+d[0],y+d[1],t+1\n            if nx>=0&&nx<n&&ny>=0&&ny<m&&

Related Tags