vuk.cpp

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