### Lời giải dùng DSU
- #### Để ý thấy rằng số ngày băng tan chính là khoảng cách ngắn nhất từ nhiều vũng nước (và 2 điểm cho trước) đến tảng băng, nên ta sẽ đẩy hết các đỉnh đó vào rồi tìm đường đi ngắn nhất đến tảng băng
- #### Muốn tìm số ngày tối thiểu để qua lại 2 điểm cần có đường đi có trọng số lớn nhất trên đường đi đó là bé nhất (trọng số ở đây chính là ngày băng tan)
- #### Ta sẽ đánh số mỗi đỉnh cho dễ và xây dựng các cạnh nối giữa các đỉnh kề nhau sau đó là tìm cây khung có 2 điểm cho trước và có trọng số lớn nhất trên cây khung là bé nhất
### Code tào đạ:
```ruby
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e3+502;
const int oo=1e18;
const int maxk=4e6+5;
struct Node{
int a,b,w;
};
bool cmp(const Node &x,const Node &y){
return x.w<y.w;
}
int n,m,dist[maxn][maxn],par[maxk],sz[maxk],id[maxn][maxn],ans=0,sta,en;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
vector<Node> edges;
string s[maxn];
queue<pair<int,int>> q;
void bfs(){
while(!q.empty()){
int x=q.front().first,y=q.front().second;
q.pop();
for (int k=0;k<4;k++){
int nx=x+dx[k],ny=y+dy[k];
if (nx<0||nx>=n||ny<0||ny>=m) continue;
if (s[nx][ny]!='X') continue;
if (dist[nx][ny]==oo){
dist[nx][ny]=dist[x][y]+1;
q.push({nx,ny});
}
}
}
}
int Find(int u){
return (u==par[u]?u:Find(par[u]));
}
void Union_set(int x,int y){
int u=Find(x),v=Find(y);
if (u==v) return;
if (sz[u]<sz[v]) swap(u,v);
par[v]=u;
sz[u]+=sz[v];
}
signed main(){
cin>>n>>m;
for (int i=0;i<maxn;i++)
for (int j=0;j<maxn;j++) dist[i][j]=oo;
for (int i=0;i<n;i++) cin>>s[i];
int d=1,ok=0;
for (int i=0;i<n;i++)
for (int j=0;j<m;j++){
if (s[i][j]=='.'||s[i][j]=='L'){
q.push({i,j});
dist[i][j]=0;
}
id[i][j]=d; par[d]=d; sz[d]=1; d++;
if (s[i][j]=='L'){
if (!ok) {sta=id[i][j]; ok=1;} else en=id[i][j];
}
}
bfs();
for (int i=0;i<n;i++)
for (int j=0;j<m;j++)
for (int k=0;k<4;k++){
int ni=i+dx[k],nj=j+dy[k];
if (ni<0||ni>=n||nj<0||nj>=m) continue;
edges.push_back({id[i][j],id[ni][nj],max(dist[i][j],dist[ni][nj])});
}
sort(edges.begin(),edges.end(),cmp);
for (int i=0;i<edges.size();i++){
if (Find(sta)==Find(en)) break; else{
ans=edges[i].w;
Union_set(edges[i].a,edges[i].b);
}
}
cout<<ans;
}
```
bacnewbie
Created at
0 likes