Intermediate.
Put your skills to the test.

Problem summary

Find the shortest safe route from S to D while water expands one grid step per minute. X blocks movement; D never floods. A person cannot enter a cell at the same time as water.

Constraints

2 ≤ R,C ≤ 250.

Worked example

Input and output for the worked example discussed below.

3 3
D.*
...
.S.

3

Solution analysis

1. First run multi-source BFS from every water cell. water[r][c] is the earliest flooding minute. Water crosses ordinary cells, including S, but cannot cross X or enter D.
2. Then run BFS from S. A proposed arrival at minute t is permitted only if the cell is passable and t<water[r][c]. D has infinite water time, so arriving there is always safe.
3. For the sample, the route from S goes left, up, up to D in three minutes. The strict inequality is important: an arrival exactly when the flood reaches a cell is forbidden. BFS explores feasible routes by increasing length, so its first arrival at D is optimal.

Why it works

Multi-source BFS gives minimum distances from the initial flood set, which are exactly water arrival times. The second BFS admits precisely moves arriving before those times. Earlier arrival never reduces future options, so one earliest visit per cell suffices. BFS therefore finds the shortest feasible route or correctly exhausts all possibilities.

Watch out. Use a strict arrival-before-flood comparison. Water cannot enter D. Mark all initial water sources before BFS rather than processing them independently.

An independently written complete program with standard headers.

#include<iostream>
#include<queue>
#include<string>
#include<utility>
#include<vector>
using namespace std;
int main(){
    int rows,columns;
    cin>>rows>>columns;
    vector<string>grid(rows);
    for(string&row:grid){
        cin>>row;
    }
    const int infinity=1000000000;
    vector<vector<int>>water(rows,vector<int>(columns,infinity));
    vector<vector<int>>distance(rows,vector<int>(columns,-1));
    queue<pair<int,int>>pending;
    pair<int,int>start;
    pair<int,int>finish;
    int dr[4]={-1,1,0,0};
    int dc[4]={0,0,-1,1};
    for(int r=0;r<rows;r++){
        for(int c=0;c<columns;c++){
            if(grid[r][c]=='*'){
                water[r][c]=0;
                pending.push({r,c});
            }
            else if(grid[r][c]=='S'){
                start={r,c};
            }
            else if(grid[r][c]=='D'){
                finish={r,c};
            }
        }
    }
    while(!pending.empty()){
        auto[r,c]=pending.front();
        pending.pop();
        for(int d=0;d<4;d++){
            int nr=r+dr[d];
            int nc=c+dc[d];
            if(nr>=0&&nr<rows&&nc>=0&&nc<columns&&grid[nr][nc]!='X'&&
                grid[nr][nc]!='D'&&water[nr][nc]==infinity){
                water[nr][nc]=water[r][c]+1;
                pending.push({nr,nc});
            }
        }
    }
    pending.push(start);
    distance[start.first][start.second]=0;
    while(!pending.empty()){
        auto[r,c]=pending.front();
        pending.pop();
        for(int d=0;d<4;d++){
            int nr=r+dr[d];
            int nc=c+dc[d];
            int arrival=distance[r][c]+1;
            // A tie with the flood is already too late.
            if(nr>=0&&nr<rows&&nc>=0&&nc<columns&&grid[nr][nc]!='X'&&
                distance[nr][nc]==-1&&arrival<water[nr][nc]){
                distance[nr][nc]=arrival;
                pending.push({nr,nc});
            }
        }
    }
    int answer=distance[finish.first][finish.second];
    if(answer==-1){
        cout<<"Impossible\n";
    }
    else{
        cout<<answer<<'\n';
    }
}