Lời giải bài tập DFS / BFS
===

-----

###### ✍️ Author: 2School Guideline
###### 📋 Content:

[TOC]

-----
# Bài 1:
**Lời giải:**

Đề yêu cầu chúng ta tính số phòng trên bản đồ, nghĩa là tính số nhóm bao gồm các chấm được kết nối với nhau.

Đoạn code sau đây có cách giải bằng phương pháp đệ quy tìm kiếm theo chiều sâu, sử dụng một mảng đánh dấu hai chiều để theo dõi các phòng đã được đi qua và hai mảng $1$ chiều thể hiện hướng đi theo tọa độ ở mỗi vị trí. Khi thuật toán tìm thấy một ô phòng chưa được đi qua, nó tăng câu trả lời lên một và lan truyền đệ quy qua các ô hàng xóm của nó và đánh dấu chúng đã được đi qua để tránh đếm lại cùng một phòng một vài lần.

**Code:**

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+5;
ll c[4]= {1,0,-1,0};
ll h[4]= {0,1,0,-1};
ll n,m,vis[N][N],ans=0;
char a[N][N];
 
 
void Read ()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            cin>>a[i][j];
}
 
void dfs(ll x,ll y)
{
    for(int i=0; i<=3; i++)
    {
        if(vis[x+c[i]][y+h[i]]==0 && a[x+c[i]][y+h[i]]=='.')
        {
            vis[x+c[i]][y+h[i]]=1;
            dfs(x+c[i],y+h[i]);
        }
    }
}
 
void Solve ()
{
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            if(vis[i][j]==0 && a[i][j]=='.')
            {
                dfs(i,j);
                ans++;
            }
    cout<<ans;
}
 
signed main ()
{
    cin.tie (0) -> sync_with_stdio(0);
    Read ();
    Solve ();
}

**Độ phức tạp:** $O(N*M)$

# Bài 2
**Lời giải:**
Ở bài này, chúng ta sử dụng thuật toán loang theo chiều rộng (**BFS**) để tìm đường đi ngắn nhất thỏa yêu cầu đề bài. Ta tiếp tục sử dụng 2 mảng một chiều $h$[ ] và $c$[ ] để lưu các hướng đi của bạn và một mảng char để lưu hướng đi bằng chữ tương ứng.

Đoạn code sau sử dụng thuật toán tìm kiếm theo chiều rộng, sử dụng một mảng 2 chiều $vis$[ ][ ] để lưu lại các điểm đã đi qua. Khi đến điểm "B", ta sẽ dừng lại và bắt đầu truy vết ngược lại đường đi theo mảng đã đánh dấu.

**Code:**

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e3+5;
ll m,n,vis[N][N],sx,sy,ex,ey;
char ans[N];
char a[N][N];
bool check=false;
ll h[4]= {1,0,-1,0};
ll c[4]= {0,1,0,-1};
char d[4]= {'D','R','U','L'};
ll dir[N][N];
 
void Read ()
{
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            cin>>a[i][j];
            if(a[i][j]=='A')
                sx=i,sy=j;
            if(a[i][j]=='B')
                ex=i,ey=j;
            vis[i][j]=0;
        }
 
}
 
 
void bfs(ll x, ll y)
{
    queue<ll> qx,qy;
    qx.push(x);
    qy.push(y);
    while(!qx.empty())
    {
        ll xx=qx.front(),yy=qy.front();
        qx.pop();
        qy.pop();
        for(int i=0; i<=3; i++)
            if(vis[xx+h[i]][yy+c[i]]==0 && xx+h[i]>0 && yy+c[i]>0 && xx+h[i]<=n && yy+c[i]<=m)
            {
                if(a[xx+h[i]][yy+c[i]]=='.')
                {
                    vis[xx+h[i]][yy+c[i]]=1;
                    dir[xx+h[i]][yy+c[i]]=i;
                    qx.push(xx+h[i]);
                    qy.push(yy+c[i]);
                }
                else if(a[xx+h[i]][yy+c[i]]=='B')
                {
                    check=true;
                    vis[xx+h[i]][yy+c[i]]=1;
                    dir[xx+h[i]][yy+c[i]]=i;
                    return;
                }
 
            }
    }
}
 
void Trace(ll x, ll y)
{
    ll t=0;
    while(x!=sx || y!=sy)
    {
        t++;
        ans[t]=d[dir[x][y]];
        ll g=x;
        x-=h[dir[g][y]];
        y-=c[dir[g][y]];
    }
    cout<<t<<"\n";
    for(int i=t; i>=1; i--)
        cout<<ans[i];
}
 
void Solve ()
{
    vis[sx][sy]=1;
    bfs(sx,sy);
    if(check==false)
    {
        cout<<"NO";
        return;
    }
    else
    {
        cout<<"YES"<<"\n";
        Trace(ex,ey);
    }
}
 
signed main ()
{
    cin.tie (0) -> sync_with_stdio(0);
    Read ();
    Solve ();
    return 0;
}

**Độ phức tạp:** $O(N*M)$

# Bài 3:

**Lời giải:**
Ta thấy quái vật di chuyển một cách tối ưu,nếu như một con quái vật đến được tới một vị trí trong bảng trước A thì A sẽ không bao giờ được tới ô đó. Do đó, để A đến một vị trí thì độ dài từ A đến vị trí đó phải ngắn hơn độ dài tất cả các quái vật đến vị trí đó.

Chúng ta sẽ sử dụng thuật toán BFS để tìm kiếm tất cả các vị trí A có thể đi tới. Chúng ta sẽ sử dụng một mảng để lưu vị trí trước đó của A để có thể truy vết lại đường đi của A trong trường hợp tồn tại đường đi để A có thể đến được bìa của bảng.

**Code:**

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 1e3 + 5;
const ll INF=1e9+5;
const int h[4] = {-1, 0, 1, 0};
const int c[4] = {0, 1, 0, -1};

int m, n, distMonster[N][N], distStarting[N][N];
int sx, sy;
bool visited[N][N];
char a[N][N];

void init() {
    queue<pair<int, int>> q;
    for(int i=0; i<=n; i++)
        for(int j=0; j<=m; j++)
            distMonster[i][j]=INF;
    for (int i = 1; i <N; ++i) {
        for (int j = 1; j <N; ++j) {
            if (a[i][j] == 'M') {
                q.push({i, j});
                distMonster[i][j] = 0;
            }
        }
    }
    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = x + h[i];
            int ny = y + c[i];
            if (nx < 1 || ny < 1 || nx > n || ny > m || a[nx][ny] == '#') continue;
            if (distMonster[x][y] + 1 < distMonster[nx][ny]) {
                distMonster[nx][ny] = distMonster[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            distStarting[i][j]=-1;
    distStarting[sx][sy] = 0;
    q.push({sx, sy});
    visited[sx][sy] = true;
    while (q.size()) {
        int x = q.front().first, y = q.front().second;
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = x + h[i];
            int ny = y + c[i];
            if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
            if (a[nx][ny] == '#' || visited[nx][ny]) continue;
            q.push({nx, ny});
            visited[nx][ny] = true;
            distStarting[nx][ny] = distStarting[x][y] + 1;
        }
    }
}

string trace(int x, int y) {
    string ans;
    while (distStarting[x][y]) {
        if (distStarting[x][y] == distStarting[x - 1][y] + 1) {
            ans += 'D';
            x--;
        }
        else if (distStarting[x][y] == distStarting[x][y - 1] + 1) {
            ans += 'R';
            y--;
        }
        else if (distStarting[x][y] == distStarting[x + 1][y] + 1) {
            ans += 'U';
            x++;
        }
        else {
            ans += 'L';
            y++;
        }
    }
    reverse(ans.begin(), ans.end());
    return ans;
}

void solve() {
    int ansX = -1, ansY = -1;
    for (int i = 1; i <= n; ++i) {
        if (distStarting[i][1] != -1 && (distStarting[i][1] < distMonster[i][1])) {
            ansX = i;
            ansY = 1;
        }
        if (distStarting[i][m] != -1 && (distStarting[i][m] < distMonster[i][m])) {
            ansX = i;
            ansY = m;
        }
    }
    for (int i = 1; i <= m; ++i) {
        if (distStarting[1][i] != -1 && (distStarting[1][i] < distMonster[1][i])) {
            ansX = 1;
            ansY = i;
        }
        if (distStarting[n][i] != -1 && (distStarting[n][i] < distMonster[n][i])) {
            ansX = n;
            ansY = i;
        }
    }
    if (ansX != -1 && ansY != -1) {
        cout << "YES\n";
        string ans = trace(ansX, ansY);
        cout << ans.size() << '\n';
        for (char c: ans) cout << c;
    }
    else cout << "NO";
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> a[i][j];
            if (a[i][j] == 'A') {
                sx = i;
                sy = j;
            }
        }
    }
    init();
    solve();
}

**Độ phức tạp:** $O(N^2)$