Bài toán
Độ phức tạp
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <queue>
#include <stack>
using namespace std;
typedef pair<int, int> ii;
#define X first
#define Y second
struct disjoint_set{
int m, n;
ii parent[550][550];
void clear(int M, int N){
m=M, n=N;
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++)
parent[i][j] = ii(i, j);
}
ii ancestor(ii u){
if (parent[u.X][u.Y]==u) return u;
else return parent[u.X][u.Y] = ancestor(parent[u.X][u.Y]);
}
void join(ii A, ii B){
//printf("join(%d %d, %d %d)\n", A.X, A.Y, B.X, B.Y);
ii x = ancestor(A);
parent[x.X][x.Y] = ancestor(B);
}
};
queue<ii> qu;
stack<ii> st;
int rx[]={-1,0,0,1};
int ry[]={0,-1,1,0};
int m, n;
char a[550][550];
int d[550][550];
bool try_adj(ii u, int& i, ii &v){
for (;;){
if (i>=4) return false;
v.X=u.X+rx[i];
v.Y=u.Y+ry[i];
if (v.X<1 or v.X>m or v.Y<1 or v.Y>n)
{ i++; continue; }
else return true;
}
}
void bfs(){
ii u, v; int i;
while (qu.size()){
u=qu.front(); qu.pop();
st.push(u);
//printf("d[%d][%d] = %d\n", u.X, u.Y, d[u.X][u.Y]);
for (i=0; try_adj(u,i,v); i++)
if (d[v.X][v.Y]==0){
d[v.X][v.Y] = d[u.X][u.Y] + 1;
qu.push(v);
}
}
}
disjoint_set djs;
main(){
int i, j; ii start, target;
scanf("%d%d", &m, &n);
for (i=1; i<=m; i++)
scanf("%s", a[i]+1);
for (i=1; i<=m; i++)
for (j=1; j<=n; j++){
if (a[i][j]=='V') start = ii(i,j);
else if (a[i][j]=='J') target = ii(i,j);
else if (a[i][j]=='+') { qu.push(ii(i,j)); d[i][j]=1; }
}
bfs();
ii u, v;
djs.clear(m, n);
while (st.size()){
u=st.top(); st.pop();
for (i=0; try_adj(u,i,v); i++){
if (d[v.X][v.Y] >= d[u.X][u.Y])
djs.join(u,v);
}
if (djs.ancestor(start) == djs.ancestor(target)){
printf("%d\n", d[u.X][u.Y]-1);
return 0;
}
}
}
Nhận xét