C++Bác nông dân qua sông - quy hoạch động (solution)

Được viết bởi: Hust IT1


Đề bài

Chỉ là một bài kiếm được trên facebook, tiện thể giải để PR web :D

Code tìm đường đi tối ưu nhất

//Hoang Son WIBU lolicon codeforces rate 1642 khong cay
#include <bits/stdc++.h>
#define F first
#define S second
#define times double stime = clock();
#define gettime cerr << "\nTime executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n";
using namespace std;
typedef long long ll;
typedef double dou;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
const ll mod = 1000000007;

//Co, Cuu, Soi. Mảng Boku là mảng điều kiện (1 = true), (2 = false)
bool boku[3][3] = {{1,0,1},
                   {0,1,0},
                   {1,0,1}};
string nameChar[3] = {"Co", "Cuu", "Soi"};
const int n = 3;
//Khai báo biến
//Mảng lưu quy hoạch động
int f[2][1 << n];
//Dùng kiểu dữ liệu priority_queue để sắp xếp các giá trị tự động trong O(log_2(n)), vị trí có số lần bước tới là ngắn nhất sẽ xử lý trước
struct ty{
    int i, j, c;
};
struct cmp{
    bool operator ()(ty &ax, ty &bx){
        return ax.c > bx.c;
    }
};
priority_queue<ty, vector<ty>, cmp> pq;
//Hàm kiểm tra điều kiện đề bài
bool check(int ax, int bx){
    if(boku[ax][bx] && boku[bx][ax]) return true;
    return false;
}
int fok[2][1 << n];
bool checkAll(int nui, int nuj){
    if(fok[nui][nuj] != -1) return fok[nui][nuj];
    bool ok = true;
    for(int i = 0; i<n; i++){
        if(nui == ((nuj >> i) & 1)) continue;
        for(int j = 0; j<n; j++){
            if(nui == ((nuj >> j) & 1)) continue;
            if(check(i, j) == false){
                ok = false;
                break;
            }
        }
        if(ok == false) break;
    }
    fok[nui][nuj] = ok;
    return fok[nui][nuj];
}
//Setup dữ liệu
void setup(){
    memset(fok, -1, sizeof fok);
    for(int i = 0; i<=1; i++){
        for(int j = 0; j<(1 << n); j++) f[i][j] = 1000000009;
    }
    f[0][0] = 0;
    pq.push({0,0,0});
}
//Thuật toán BFS -> https://cowboycoder.tech/article/ly-thuyet-do-thi-co-ban-tim-kiem-theo-chieu-rong-tren-do-thi-breadth-first-search-bfs
void BFS(){
    while(!pq.empty()){
        ty u = pq.top(); pq.pop();
        if(f[u.i][u.j] != u.c) continue;
        if(u.i == 1 && u.j == (1 << n) - 1) break;
        for(int i = 0; i<n; i++){
            if(u.i == ((u.j >> i) & 1)){
                int nui = u.i ^ 1;
                int nuj = u.j ^ (1 << i);
                bool ok = checkAll(nui, nuj);
                if(ok){
                    if(f[nui][nuj] > u.c + 1){
                        f[nui][nuj] = u.c + 1;
                        pq.push({nui, nuj, u.c + 1});
                    }
                }
            }
        }
        //Xét trường hợp thuyền thay đổi vị trí nhưng không mang theo con vật nào cả
        int nui = u.i ^ 1;
        int nuj = u.j;
        if(checkAll(nui, nuj)){
            if(f[nui][nuj] > u.c + 1){
                f[nui][nuj] = u.c + 1;
                pq.push({nui, nuj, u.c + 1});
            }
        }
    }
}
//Main
void process(){
    setup();
    BFS();
    //Trace từ vị trí đích về vị trí xuất phát
    int ui = 1, uj = (1 << n) - 1;
    vector<pii> res(0);
    while(ui != 0 || uj != 0){
        int nui = ui ^ 1;
        int nuj = uj;
        if(f[ui][uj] == f[nui][nuj] + 1){
            res.push_back({-1, ui});
            ui = nui; uj = nuj;
            continue;
        }
        for(int i = 0; i<n; i++){
            if(ui == ((uj >> i) & 1)){
                nui = ui ^ 1;
                nuj = uj ^ (1 << i);
                if(f[ui][uj] == f[nui][nuj] + 1){
                    res.push_back({i, ui});
                    ui = nui; uj = nuj;
                    break;
                }
            }
        }
    }
    //Hàm đảo ngược mảng
    reverse(res.begin(), res.end());
    //Pint min value of way
    cout << f[1][(1 << n) - 1] << "\n";
    //Print way
    for(pii i: res){
        if(i.S == 0) if(i.F != -1) cout << nameChar[i.F] << " ->\n";
        if(i.S == 1) if(i.F != -1) cout << "<- " << nameChar[i.F] << "\n";
        if(i.F == -1){
            if(i.S == 0) cout << "->\n";
            if(i.S == 1) cout << "<-\n";
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

Giải thích

Quy hoạch động $f[2][1 << n]$, trong đó $2$ là trạng thái của thuyền, $(1 << n)$ là trạng thái của n con vật (mỗi bit tương ứng với trạng thái trái phải của con vật). Mỗi lần di chuyển thuyền ta có $n + 1$ cách chọn, trong đó $n$ là cách chọn có con vật đi theo, $+1$ là cách chọn không có con vật nào đi theo. Như vậy bài này có thể quy về tìm đường đi ngắn nhất giữa $(1 << (n + 1))$ đỉnh. Ngoài ra để giảm độ phức tạp ta lưu lại các trạng thái thỏa mãn điều kiện đề bài vào mảng $fok[2][1 << n]$

Bài toán này cũng áp dụng thêm quy hoạch động trạng thái -> https://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/tutorial/

Bạn có thể xem thêm về dynamic programming -> https://vnoi.info/wiki/translate/topcoder/dynamic-programming.md

Lưu ý: $1 << n$ tương đương với $2^n$ nhưng $1 << n$ tốc độ nhanh hơn so với $2^n$ (thao tác bit máy tính xử lý nhanh hơn)

Độ phức tạp

$$ O(2^{n+1} . log_2(2^{n+1}) . (n+1) + 2^{n+1} . n^2) \approx O(2 . 2^{n+1} . n^2)$$

Ngoài ra thì nếu bạn chỉ cần in một phương án bất kỳ ra màn hình thì bạn chỉ cần trace và tìm đường đi không trùng lặp, độ phức tạp sẽ giảm xuống còn:

$$ O(2^{n+1} . (n+1) + 2^{n+1} . n^2) \approx O(2^{n+1} . n^2)$$

Posted on July 04, 2021 09:51:27 PM


6
Donate free




Đăng nhập để tham gia thảo luận! Hoặc bạn có thể bình luận bằng facebook ở dưới.