Ứng dụng của đồ thị

Ta đang sống trong một thế giới mà mọi vật được liên kết, các thành phố được liên kết với nhau bởi các con đường, con người liên kết với nhau trên mạng xã hội… những liên kết như vậy chính là hình hài của đồ thị. Một trong những đồ thị lớn mà ai trong chúng ta cũng biết đó chính là Internet hay là mạng tìm kiếm Google.

Đồ thị được sinh ra từ nhu cầu giải quyết những vấn đề thực tế của đời sống. Ví dụ như là bài toán ‘7 cây cầu Königsberg’ từ những năm 1720. Đồ thị là một phần quan trọng trong Toán học rời rạc, là cơ sở của Tin học. Ứng dụng của nó vô cùng rộng, áp dụng vào trong nhiều lĩnh vực. Trong phạm vi bài viết, tác giải chỉ đề cập đến một vài ứng dụng thực tế cơ bản.

Bài toán bảy cây cầu

Tìm đường đi ngắn nhất

Trong thực tế, ta luôn phải lựa chọn đường đi ngắn nhất để đi sao cho tiết kiệm xăng. Đầu tiên là biểu diễn mạng giao thông dưới dạng đồ thị rồi sử dụng thuật toán tìm đường đi ngắn nhất. Thường thì mọi người sử dụng thuật toán Dijkstra nhưng giả dụ với dữ liệu không lồ như của Google Map thì thuật toán này không thể đáp ứng. Google đang sử dụng một thuật toán có tộc độ nhanh hơn nhiều thuật toán Dijkstra.

Tìm đường trên Google Maps

Nhưng nếu muốn tìm đường giữa Hà Nội và New York thì sao? Giữa chúng có hàng tỉ tỉ giao lộ thì phải làm thế nào?

 

Tô màu đồ thị

Ứng dụng điển hình của tô màu đồ thị là bài toán tô màu bản đồ. Làm sao để tô màu bản đồ sao cho không có hai vùng kề nhau có cùng màu và số màu cần dùng là ít nhất.

Biểu diễn bài toán dưới dạng đồ thị:

  • Coi mỗi vùng là một đỉnh
  • Hai đỉnh có cạnh nối với nếu hai vùng tương ứng kề nhau

Bài toán trở thành tô màu các đỉnh của đồ thị, giải quyết sẽ đơn giản hơn bài toán ban đầu.

Bài toán tô màu bản đồ

Một ứng dụng khác là trong bài toán xếp lịch ở UET, làm sao để xếp lịch thi cho sinh viên sao cho nếu sinh viên học môn A và môn B thì hai môn này không thi cũng lúc, ngoài ra kì thi cần kết thúc sớm nhất.

Với bài này ta giải quyết thế nào?

Gọi mỗi môn học là một đỉnh, hai đỉnh được nỗi với nhau nếu tồn tại học sinh học cả 2 môn này. Bài toán giờ trở thành bài toán tô màu cho các đỉnh.

 

Đồ thị hai phía

graph-yeulaptrinh.pw

Đồ thị ghép cặp hẹn hò

Đồ thị hai phía thường được dùng để mô hình các bài toán ghép cặp, quan hệ hôn nhân giữa tập những người đàn ông và tập những người phụ nữ, sinh viên chọn trường, thầy giáo chon tiết dạy trong thời khóa biểu v.v…

 

QHROAD – spoj

Đề bài:

Thuật toán:

  • Kruskal những đoạn đường không bị phá.
  • Duyệt các truy vấn từ Q về 1. Nếu join thì giảm số tplt

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second+++
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E5+3;
const ll oo = 1e18+3;
 
struct  edge {
	int u,v;
} e[MAXN];
int n, m, q, pa[MAXN], u , v, x, a[MAXN], tplt, ans[MAXN];
bool dt[MAXN];
 
int find(int u) {
	if (pa[u]!=u) pa[u] = find(pa[u]);
	return pa[u];
}
 
bool join(int u, int v) {
	int i = find(u);
	int j = find(v);
	if (i==j) return 0;
	else
	pa[i] = j;
	return 1;
}
 
int main() {
	cin >> n >> m >> q;
	FOR(i,1,m) {
		cin >> e[i].u >> e[i].v;
	}
	FOR(i,1,q) {
		cin >> x;
		dt[x] = 1;
		a[i] = x;
	}
	tplt = n;
	FOR(i,1,n) pa[i] = i;
	FOR(i,1,m)
	if (!dt[i]) {
		if (join(e[i].u,e[i].v)) tplt--;
	}
	FORD(i,q,1) {
		ans[i] = tplt;
		int id = a[i];
		if (join(e[id].u,e[id].v)) tplt--;
	}
	FOR(i,1,q) cout << ans[i] << endl;
   	return 0;
}

QBMST – spoj

Đề bài:

Thuật toán:

Code:

#include <iostream>
#include <vector>
#include <algorithm> // Hàm sort
using namespace std;
 
// Cấu trúc để lưu cạnh đồ thị,
// u, v là 2 đỉnh, w là trọng số cạnh
struct edge {
    int u, v, w;
};
// Hàm so sánh để dùng trong hàm sort ở dưới
bool cmp(const edge &a, const edge &b) {
    return a.w < b.w;
}
 
// Số đỉnh tối đa trong đề bài
#define N 10005
 
// 2 mảng sử dụng trong Disjoint Set
int cha[N], hang[N];
 
// Tìm xem u thuộc cây nào
int find(int u) {
    if (cha[u] != u) cha[u] = find(cha[u]);
    return cha[u];
}
 
// Hợp nhất 2 cây chứ u và v,
// Trả về false nếu không thể hợp nhất
bool join(int u, int v) {
    u = find(u); v = find(v);
    if (u == v) return false;
    if (hang[u] == hang[v]) hang[u]++;
    if (hang[u] < hang[v]) cha[u] = v;
    else cha[v]=u;
    return true;
}
 
int main() {
    // Thêm dòng này để cin, cout chạy nhanh
    ios::sync_with_stdio(false); cin.tie(0);
 
    // Nhập vào số đỉnh và số cạnh
    int n, m; cin >> n >> m;
 
    // Nhập danh sách các cạnh
    vector<edge> edges(m);
    for (edge &e: edges) cin >> e.u >> e.v >> e.w;
 
    // Sắp xếp lại các cạnh theo trọng số tăng dần
    sort(edges.begin(), edges.end(), cmp);
 
    // Khởi tạo cấu trúc Disjoint Set
    for (int i=1; i<=n; i++) {
        cha[i] = i;
        hang[i] = 0;
    }
 
    // Lưu tổng trọng số các cạnh trong cây khung nhỏ nhất
    int mst_weight = 0;
 
    // Duyệt qua các cạnh theo thứ tự đã sắp xếp
    for (edge &e: edges) {
        // Thử hợp nhất 2 cây chứa u và v
        if (join(e.u, e.v)) {
            // Hợp nhất thành công, ta thêm e và kết quả
            mst_weight += e.w;
        }
    }
 
    // Xuất kết quả
    cout << mst_weight;
    return 0;
}
const   fi='';
        fo='';
        maxn=10003;
        maxc=trunc(1e9);
        maxm=15000;
var     link,head,ke,ts :array[-maxm..maxm] of longint;
        i,j,n,m :longint;
        d       :array[1..maxn] of longint;
        h,p     :array[1..maxn] of longint;
        nh,res  :longint;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
procedure enter;
var     i,u,v,w :longint;
begin
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(u,v,w);
                        add(i,u,v,w);
                        add(-i,v,u,w);
                end;
        close(input);
end;
procedure swap(var x,y:longint);
var     tg      :longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if d[h[j]]>d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]] , p[h[j]] );
                        upheap(j);
                end;
end;
procedure downheap(i:longint);
var     j :longint;
begin
        j:=i+i;
        if j>nh then exit;
        if (j<nh) and (d[h[j]]>d[h[j+1]]) then inc(j);
        if d[h[i]]>d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]] , p[h[j]]);
                        downheap(j);
                end;
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else
                begin
                        upheap(p[i]);
                end;
end;
procedure process;
var     i,u,v   :longint;
begin
        for i:=1 to n do
                d[i] := maxc;
        d[1] := 0; push(1);
        repeat
                u:=pop;
                res := res + d[u];
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>ts[i] then
                                        begin
                                                d[v]:=ts[i];
                                                update(v);
                                        end;
                                i := link[i];
                        end;
        until nh=0;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

QBSCHOOL – spoj

Đề bài:

Thuật toán:

  • Gọi Gọi f[i] và d[i] lần lượt là độ dài và số đường đi ngắn nhất từ đỉnh 1 đến đỉnh i.
  • Để tính d[i] ta sử dụng thuật toán Dijkstra
  • Để tính số lượng đường đi ngắn nhất giữa hai đỉnh ta tính như sau
  • Nếu d[v]>d[u]+c(u,v), ta gán d[v]=d[u]+c(u,v) và f[v]=f[u]

    Nếu d[v]=d[u]+c(u,v) thì gán f[v]=f[v]+f[u].

    (có thể xem rõ hơn ở code bên dưới)

Code:

const   fi      ='';
        fo      ='';
        maxn    =30000+3;
        maxc    =trunc(1e9)+3;
        maxm    =trunc(1e5);
type    arrd    =array[1..maxn] of longint;
        arrf    =array[1..maxn] of int64;
        arrk    =array[-maxm..maxm] of longint;
        arrh    =array[1..maxn] of longint;
var     d1,dn,d   :arrd;
        f1,fn,f   :arrf;
        n,i,j,m   :longint;
        res     :longint;
        ans     :arrd;
        head :array[1..maxn] of longint;
        link,ts,ke    :arrk;
        // dijkstra heap;
        h,p     :array[1..maxn] of longint;
        nh      :longint;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
procedure enter;
var     u,v,w,k:longint;
begin
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(k,u,v,w);
                        add(i,u,v,w);
                        if k=2 then add(-i,v,u,w);
                end;
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if d[h[i]] < d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        upheap(j);
                end;
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and (d[h[j]] > d[h[j+1]]) then inc(j);
        if d[h[j]] < d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        downheap(j);
                end;
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else upheap(p[i]);
end;
procedure dijkstra(s:longint);
var     u,v,i:longint;
begin
        fillchar(h,sizeof(f),0);
        fillchar(p,sizeof(p),0);
        nh:=0;
        fillchar(f,sizeof(f),0);
        for i:=1 to n do d[i]:=maxc;
        d[s]:=0;
        f[s]:=1;
        push(s);
        repeat
                u:=pop;
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>d[u]+ts[i] then
                                        begin
                                                d[v]:=d[u]+ts[i];
                                                f[v]:=f[u];
                                                update(v);
                                        end
                                        else
                                if d[v]=d[u]+ts[i] then
                                        begin
                                                f[v]:=f[u]+f[v];
                                        end;
                                i:=link[i];
                        end;
        until nh=0;
end;
procedure process;
begin
        dijkstra(1);
        f1:=f;
        d1:=d;
        dijkstra(n);
        fn:=f;
        dn:=d;
        for i:=1 to n do
                if (d1[i]+dn[i]<>d1[n])
                or (f1[i]*fn[i]<>f1[n]) then
                        begin
                                inc(res);
                                ans[res]:=i;
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(d1[n],' ',f1[n]);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
typedef pair<long long, int> lli;
 
const long long oo = ((1 << 30)-1)*2-1;
const int max_n = 5000+1;
 
int n, m;
long long min_d, dist = 0, f[max_n];
vector<lli> adj[max_n];
 
inline void load_map()
{
    cin >> n >> m;
    int type, u, v, w;
    while (m--)
    {
        cin >> type >> u >> v >> w;
        adj[u].push_back(lli(w, v));
        if (type==2) adj[v].push_back(lli(w, u));
    }
}
 
inline void dijkstra()
{
    vector<lli>::iterator it;
    long long cuv, du, d[max_n];
    int u, v;
    priority_queue<lli, vector<lli>, greater<lli> > heap;
    for (u=1; u <= n; u++) d[u] = +oo;
    memset(f, 0, sizeof(f));
    d[1] = 0; f[1] = 1;
    heap.push(lli(0, 1));
    while (heap.size())
    {
        du = heap.top().first; u = heap.top().second;
        heap.pop();
        if (du != d[u]) continue;
        if (u == n) break;
        for (it=adj[u].begin(); it != adj[u].end(); it++)
        {
            cuv = it->first; v = it->second;
            if (d[v]==d[u]+cuv) f[v] += f[u];
            if (d[v] > d[u]+cuv)
            {
                d[v] = d[u]+cuv;
                f[v] = f[u];
                heap.push(lli(d[v], v));
            }
        }
    }
    min_d = d[n];
}
 
main()
{
    load_map();
    dijkstra();
    cout << min_d << " " << f[n];
}

COMNET – spoj

Đề bài:

Tóm tắt đề:

Cho M đường truyền có các chi phí wi, các truy vấn người ta thay đổi trọng số một số cạnh và hỏi xem cạnh thứ k có thể loại bỏ vì nó không thuộc vào cây khung nhỏ nhất của đồ thị hay không.

Thuật toán:

-Sau khi thay đổi trọng số các cạnh theo đề bài (nếu các cạnh có trọng số bằng nhau thì ưu tiên xét cạnh k đứng đầu), tìm cây khung nhỏ nhất của đồ thị và in ra ‘YES’ hay ‘NO’ tương ứng là cây trả lời. ĐPT O(test*nlogn)
-Thuật toán trên sẽ giúp bạn có được 60->70 điểm, đề ăn full bạn cần thay đổi một chút trước khi tìm cây khung: Vẫn thay đổi trọng số các cạnh theo đề bài, nhưng không sort lại các cạnh mà tìm các cạnh có trọng số nhỏ hơn trọng số của cạnh thứ k, hợp nhất các gốc lại.

Kiểm tra xem hai đỉnh của cạnh thứ k đã thuộc vào cây khung hay chưa rồi in ra ‘YES’ hay ‘NO’ tương ứng. ĐPT O(test*n).

Code:

#include <iostream>
#include <vector>
using namespace std;
 
#define LL long long
 
struct universe {
    vector<int> cha, rank;
    universe(int n): cha(n + 1), rank(n + 1, 0) {
        for (int i=1; i<=n; i++) cha[i] = i;
    }
    int find(int u) {
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u] > rank[v]) cha[v] = u;
        else cha[u] = v;
        return true;
    }
};
 
struct pack { int u, v; };
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m, Q; cin >> n >> m >> Q;
        vector<pack> e(m);
        vector<int> w(m);
        for (int i=0; i<m; i++) cin >> e[i].u >> e[i].v >> w[i];
        while (Q--) {
            int id; cin >> id; id--;
            int s; cin >> s;
            vector<int> ww(w);
            while (s--) {
                int t, w; cin >> t >> w;
                ww[t-1] = w;
            }
            universe a(n);
            for (int i=0; i<m; i++) if (ww[i] < ww[id]) {
                a.join(e[i].u, e[i].v);
            }
            if (a.join(e[id].u, e[id].v)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
    return 0;
}

LUBENICA – spoj

Đề bài:

Thuật toán:

  • LCA

Code:

uses    math;
const   fi='';
        fo='';
        maxk=20;
        maxn=trunc(1e5)+3;
        oo=2*trunc(1e9);
 
type    arr1    =array[1..maxn] of longint;
        arr2    =array[1..maxn,0..maxk] of longint;
 
var     mi,ma,p         :arr2;
        depth,dad       :arr1;
        i,j,n,m,q       :longint;
        link,head,ke,ts :array[-maxn..maxn] of longint;
        resma,resmi     :longint;
        cx      :array[1..maxn] of boolean;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
 
procedure enter;
var     u,v,w   :longint;
begin
        readln(n);
        for i:=1 to n-1 do
        begin
                read(u,v,w);
                add(i,u,v,w);
                add(-i,v,u,w);
        end;
end;
 
procedure dfs(u:longint);
var     i,v     :longint;
begin
        cx[u]:=false;
        i := head[u];
        while i<>0 do
                begin
                        v:=ke[i];
                        if cx[v] then
                                begin
                                        depth[v]:=depth[u]+1;
                                        dad[v]:=u; ma[v,0] := ts[i]; mi[v,0] := ts[i];
                                        dfs(v);
                                end;
                        i:=link[i];
                end;
end;
 
procedure init;
var     i,j     :longint;
begin
        fillchar(cx,sizeof(cx),true);
        dad[1] := 1; depth[1] :=1;
        dfs(1);
        for i:=1 to n do
                begin
                        p[i,0] := dad[i];
                end;
        for j:=1 to maxk do mi[1,0] := oo;
        for j:=1 to maxk do ma[1,0] := -oo;
        for j:=1 to maxk do
                for i:=1 to n do
                        begin
                                p[i,j] := p[p[i,j-1],j-1];
                                ma[i,j] := max(ma[i,j-1],ma[p[i,j-1],j-1]);
                                mi[i,j] := min(mi[i,j-1],mi[p[i,j-1],j-1]);
                        end;
end;
procedure lca(u,v:longint);
var     i,j     :longint;
begin
        for i:=maxk downto 0 do
                if depth[p[u,i]]>=depth[v] then
                        begin
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                u := p[u,i];
                        end;
        for i:=maxk downto 0 do
                if depth[p[v,i]]>=depth[u] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                v := p[v,i];
                        end;
        if u=v then exit;
        for i:=maxk downto 0 do
                if p[u,i]<>p[v,i] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                v := p[v,i];
                                u := p[u,i];
                        end;
        resma := max(resma,ma[v,0]);
        resmi := min(resmi,mi[v,0]);
        resma := max(resma,ma[u,0]);
        resmi := min(resmi,mi[u,0]);
end;
procedure process;
var     u,v,qq  :longint;
begin
        read(q);
        for qq:=1 to q do
                begin
                        read(u,v);
                        if u=v then begin writeln(0,' ',0); continue; end;
                                resmi := oo;
                                resma := -oo;
                                lca(u,v);
                        writeln(resmi,' ',resma);
                end;
end;
procedure print;
begin
 
end;
 
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
                enter;
                init;
                process;
                print;
        close(input);close(output);
end

LABUDOVI – spoj

Đề bài:

Thuật toán:

  • BFS
  • Bài này chú ý dùng phương pháp loang đồ thị để làm; chúng ta sẽ dùng 2 mảng nextx, nexty để loang ra 4 ô xung quanh của 1 ô.
  • Đầu tiên đánh dấu vị trí của 2 con thiên nga và đánh dấu tất cả các ô là nước.
  • Sau đó tiến hành loang từ con thiên nga thứ nhất. Nếu gặp con thiên nga thứ hai thì return.
    Nếu không thì tiến hành loang các ô bên cạnh là ô băng; nếu gặp ô băng thì chuyển thành ô nước, đánh dấu lại và tăng biến đếm lên 1. Tiếp tục như vậy cho tới khi gặp được con thiên nga thứ hai.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
 
#define task ""
#define fi first
#define se second
#define maxinp (int)(1500)
#define MODUL (int)(1e9+57)
#define siz(x) (int)(x.size())
#define len(x) (int)(x.length())
#define whole(x) x.begin(), x.end()
#define FOR(i, x, y) for(int i=x; i<=y; ++i)
#define FORl(i, x, y) for(int i=x; i<y; ++i)
#define FORb(i, x, y) for(int i=x; i>=y; --i)
#define FORlb(i, x, y) for(int i=x; i>y; --i)
#define MEMS(x, val) memset(x, val, sizeof(x))
#define FILEOP(x) freopen(x".inp", "r", stdin); freopen(x".out", "w", stdout);
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef queue<ii> qii;
typedef long long ll;
int nextx[4] = {-1, 0, 0, 1};
int nexty[4] = {0, -1, 1, 0};
bool Free[maxinp][maxinp];
int Time[maxinp][maxinp];
char a[maxinp][maxinp];
int m, n, res, nTime;
qii mainq, subq;
ii start[3];
int nInstruction = 0;
void Debug()
{
 
    cout << endl;
    FOR(i, 1, m)
    {
        FOR(j, 1, n)
        {
            cout << Time[i][j] << " ";
        }
        cout << endl;
    }
    cout << endl;
 
 
}
 
 
void Enter()
{
	int cnt = 1;
	MEMS(Free, true);
 
 
	scanf("%d%d", &m, &n);
 
 
 
 
	FOR(i, 1, m)
	{
	    FOR(j, 1, n)
	    {
 
	        cin >> a[i][j];
 
 
            if(a[i][j] != 'X')
            {
                Time[i][j] = 0;
 
                mainq.push(ii(i, j));
 
                if(a[i][j] == 'L')
                {
                    start[cnt] = ii(i, j);
                    ++cnt;
                }
 
                Free[i][j] = false;
            }
            else Time[i][j] = 1234567890;
 
            ++nInstruction;
 
 
	    }
	}
 
}
 
//Check
bool IsValid(int _x, int _y)
{
    return(_x >= 1 && _y >= 1 && _x <= m && _y <= n && Free[_x][_y]);
}
 
void PreProcess()
{
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        ++nInstruction;
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
 
            if(IsValid(x, y))
            {
                if(a[x][y] == 'X')
                {
                    Free[x][y] = false;
                    mainq.push(ii(x, y));
                    Time[x][y] = min(Time[x][y], Time[curx][cury] + 1);
                }
            }
        }
 
    }
 
    //Debug();
 
 
 
}
void FloodFill1(ii st1, ii st2)
{
    mainq.push(st1);
    Free[st1.first][st1.second] = false;
    while(!mainq.empty())
    {
        int curx = mainq.front().first;
        int cury = mainq.front().second;
 
        //Time[curx][cury] = nTime;
        ++nInstruction;
 
        mainq.pop();
 
        FOR(i, 0, 3)
        {
            int x = curx + nextx[i];
            int y = cury + nexty[i];
            ii dir = ii(x, y);
 
            if(IsValid(x, y))
            {
                Free[x][y] = false;
                if(dir == st2) return;
                if(Time[x][y] <= res) mainq.push(dir);
                else subq.push(dir);
            }
        }
 
        if(mainq.empty())
        {
            ++res;
            swap(mainq, subq);
        }
 
    }
}
 
//Process
void Solve()
{
    res = 0;
    PreProcess();
    MEMS(Free, true);
    FloodFill1(start[1], start[2]);
    printf("%d", res);
 
 
    cerr << endl;
    cerr << nInstruction << endl;
 
}
 
//Main Procedure
int main()
{
    Enter();
    Solve();
    return 0;
}