Subtask ~1~

• Tìm kiếm nhị phân : Với mỗi giá trị ~mid~, ta sẽ tìm đường đi từ S đến E thỏa mãn khoảng cách từ ô đang xét đến các ô # không nhỏ hơn ~mid~. Nếu tìm được đường đi thỏa mãn thì cập nhật kết quả là ~mid~ và tìm kiếm nhị phân từ ~mid + 1 \to R~, ngược lại tìm kiếm nhị phân từ ~L \to mid - 1~.
• Độ phức tạp: ~O(N^3logN)~.

Subtask ~2~

• Gọi ~d[i][j]~ là khoảng cách từ ô (~i~,~j~) đến ô thú dữ gần nhất (hay ô có ký tự # gần nhất). Ta có thể tìm d[~i~][~j~] trước bằng cách duyệt BFS/DFS từ các ô # đến những ô còn lại.
• Tìm kiếm nhị phân : Với mỗi giá trị ~mid~, ta sẽ tìm đường đi từ S đến E sao cho : ~ \forall ~ ô (~i~,~j~) trên đường đi, ~ d[i][j] \geq mid ~. Nếu tìm được đường đi thỏa mãn thì cập nhật kết quả là ~mid~ và tìm kiếm nhị phân từ ~mid + 1 \to R~, ngược lại tìm kiếm nhị phân từ ~L \to mid - 1~.
• Độ phức tạp: ~O(N^2logN)~.

  Code tham khảo

#include<bits/stdc++.h>
#define reu(i,a,b) for(int i=a,_b=b;i<=_b;++i)
#define red(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define mp make_pair
#define ll long long
#define ii pair<int,int>
#define fi first
#define se second
#define iii pair<int,pair<int,int> >
#define sz(x) int(x.size())
using namespace std;
const int N = 1003;
const int oo = 1e9 + 7;

int X[]={0, 1, 0, -1, 0};
int n, m, d[N][N];
queue<ii> q;
ii s, t;
bool isfree[N][N];

void input()
{
    memset(d, 0x3f, sizeof(d));
    char x;
    cin >> n >> m;
    reu(i,1,n) reu(j,1,m)
    {
        cin >> x;
        if(x == '#')
        {
            q.push({i, j});
            d[i][j] = 0;
        }
        if(x == 'S') s = {i, j};
        if(x == 'E') t = {i, j};
    }
}

bool check(int k)
{
    if(d[s.fi][s.se] < k) return false;
    reu(i, 1, n) reu(j, 1, m) isfree[i][j] = true;
    isfree[s.fi][s.se] = false;
    q.push(s);
    while(sz(q))
    {
        int u = q.front().fi, v = q.front().se;
        q.pop();
        reu(i, 0, 3)
        {
            int x = u + X[i], y = v + X[i + 1];
            if(x <= n && y <= m && x > 0 && y > 0 && isfree[x][y] && d[x][y] >= k)
            {
                isfree[x][y] = false;
                q.push({x,y});
            }
        }
    }
    return (!isfree[t.fi][t.se]);
}

void solve()
{
    while(sz(q))
    {
        int u = q.front().fi, v = q.front().se;
        q.pop();
        reu(i, 0, 3)
        {
            int x = u + X[i], y = v + X[i + 1];
            if(x <= n && y <= m && x > 0 && y > 0 && d[x][y] > d[u][v] + 1)
            {
                d[x][y] = d[u][v] + 1;
                q.push({x, y});
            }
        }
    }
    int l = 0, r = N * 2, res = r;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(check(mid))
        {
            res = mid;
            l = mid + 1;
        } else r = mid - 1;
    }
    cout <<  res;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    input();
    solve();
    return 0;
}