thảo luận [Học Tập] Topic thuật toán

unknowpc90

unknowpc90

Junior Member
Chào các bác,

Em đang cần giải quyết một thuật toán tìm đường đi trong lập trình
Yêu cầu là tìm đường đi từ A đến B và tất cả các đường có kết nối với quãng đường cần đi đó, mỗi điểm trên đường đi đều có toạ độ (x,y)
Nó giống như dòng nước sẽ chảy từ nguồn nước đến bên ngoài thông qua hệ thống uống nước và yêu cầu tìm tất cả đường đi mà nước có thể chạm tới.
Ví dụ như hình:
2020c372da18-82cf-42eb-a3ad-36d00d2c977f.png

Theo hình trên, nước sẽ chảy từ trái qua phải (chảy tới vùng màu vàng), vì thế điểm bắt đầu là (1,3) và chảy đến điểm cuối là (5,6). Trên đường đi, nước sẽ chảy qua các điểm khác. Tất cả điểm nước chảy qua được đều tô màu đỏ
Khả năng hiện có: có thể xác định điểm đầu là (1,3) và điểm cuối là (5,6). Có thể xác định những điểm kết nối với nó, chẳng hạn điểm đầu là (1,3) thì có thể biết điểm kết nối với nó là (2,3).
Như hình trên, kết quả của thuật toán em mong muốn sẽ trả về 3 chuỗi:
Chuỗi 1: (1,3), (2,3), (2,4), (2,5), (3,5), (3,6), (4,6), (5,6) [đường đi nước chảy từ điểm đầu đến điểm cuối]
Chuỗi 2: (1,3), (2,3), (2,4), (2,5), (3,5), (3,6), (3,7), (3,8), (2,8) [đường đi nước có thể chảy lan tới]
Chuỗi 3: (1,3), (2,3), (2,2), (2,1), (3,1) [đường đi nước có thể chảy lan tới]
Các bác góp ý cách viết thuật toán cho em nhé. Thanks!
 
Last edited:
- Lý thuyết đồ thị
Bạn thiết lập một ma trận với các điểm có giá trị
+ (rỗng) : ko có đường đi
+ 1:có đường đi
+ hoặc 2...n: Nếu khoảng cách giữa 2 điểm lớn hơn 1 (nhằm mục đích tìm đường đi ngắn nhất nếu muốn)
-----------
Áp dụng một số giải thuật: Dijkstra, Bellman-Ford, Giải thuật tìm kiếm A*, Floyd-Warshall
Hoặc đơn giản hơn thì vét cạn, mà hơi thường thì ít dùng vì tốn chi phí :)
 
Đây là bài toán tìm đường đi ngắn nhất nhưng không dừng lại khi tìm được đáp án mà tiếp tục chạy cho đến khi tìm được hết các đường đi. Có nhiều giải thuật có thể áp dụng nhưng nếu chịu khó thớt implement cái A* đi, bữa tôi đi phỏng vấn mà họ bắt code A* cho một cái mini game tương tự, kiểu nối các ô có màu giống nhau trong cái đồ thị trên, mà làm trong 30 phút thôi, kết quả là tạch. :feel_good:
 
zzchaolegionzz said:
Đây là bài toán tìm đường đi ngắn nhất nhưng không dừng lại khi tìm được đáp án mà tiếp tục chạy cho đến khi tìm được hết các đường đi. Có nhiều giải thuật có thể áp dụng nhưng nếu chịu khó thớt implement cái A* đi, bữa tôi đi phỏng vấn mà họ bắt code A* cho một cái mini game tương tự, kiểu nối các ô có màu giống nhau trong cái đồ thị trên, mà làm trong 30 phút thôi, kết quả là tạch. :feel_good:
Click to expand...
Bác ơi, cái này không phải tìm đường đi ngắn nhất, mà là tìm đường đi từ A đến B thôi với điều kiện là đường đi thông suốt nghĩa là các điểm có nối với nhau, xong rồi phải tìm ra các đường có nối (thông suốt) với đường đi đã tìm đó
 
jenTran said:
ko thấy quy tắc gì vậy? Sao nó ko đi tới 1:5 luôn
Click to expand...
Nó không đi từ 1 tới 5 luôn vì các điểm đó không nối với nhau nên không tạo thành đường đi.
Trên hình minh hoạ, mình tô màu đỏ là các điểm có nối với nhau tạo thành các đường đi
Cái mình đang có: toạ độ điểm đầu, toạ độ điểm cuối, một hàm trả về các điểm kết nối với một điểm nhập vào
Cái mình cần: đường đi từ điểm đầu đến điểm cuối, tất cả đường đi kết nối với đường đi đó, tất cả các điểm trong mỗi đường đi kể trên
 
Last edited:
unknowpc90 said:
Bác ơi, cái này không phải tìm đường đi ngắn nhất, mà là tìm đường đi từ A đến B thôi với điều kiện là đường đi thông suốt nghĩa là các điểm có nối với nhau, xong rồi phải tìm ra các đường có nối (thông suốt) với đường đi đã tìm đó
Click to expand...
Bạn ấy nói đúng rồi còn gì
Bài này có thể sử dụng thuật toán tìm đg đi ngắn nhất
Nhưng thay vì chỉ đưa ra đường đi ngắn nhất thì đưa ra mọi đường đi có khả năng
 
Xin chào mọi người, vì mục tiêu hướng tới lương 5k 6k nên em lập thread này.
Mỗi ngày làm tối thiểu một bài trên Leetcode, ai có solution hay thì post lên cho mọi người tham khảo, ai không làm được có thể hỏi mọi người.
Mục đích chính để luyện cấu trúc dữ liệu và giải thuật :matrix:

Ai có problems hay thì post lên em sẽ tổng hợp ở #1 :big_smile:

Bài 1: [Easy] Min Stack
Bài 2: [Easy] - Longest palindrome - Đóng góp @BadCoder
Bài 3: [Medium] Valid Parenthesis String - Bài này dấu ngoặc đúng dùng stack điển hình này, nhưng nó cho thêm cái dấu * vào khá hay đó :big_smile:
 
Last edited:
[IamNormal] said:
Xin chào mọi người, vì mục tiêu hướng tới lương 5k 6k nên em lập thread này.
Mỗi ngày làm tối thiểu một bài trên Leetcode, ai có solution hay thì post lên cho mọi người tham khảo, ai không làm được có thể hỏi mọi người.
Mục đích chính để luyện cấu trúc dữ liệu và giải thuật :matrix:

Ai có problems hay thì post lên em sẽ tổng hợp ở #1 :big_smile:

Bài 1: [Easy] Min Stack
Click to expand...
C-like: 
class MinStack {
private:
    vector<int> results;
    vector<int> min_;
public:
    /** initialize your data structure here. */
 
    MinStack() {
      
    }
 
    void push(int x) {
        results.push_back(x);
        if (min_.size() == 0 || x < min_.back()) min_.push_back(x);
        else (min_.push_back(min_.back()));
    }
 
    void pop() {
        results.pop_back();
        min_.pop_back();
    }
 
    int top() {
        return results.back();
    }
 
    int getMin() {
        return min_.back();
    }
};
 
Last edited by a moderator:
Sao thằng này có mỗi 1 test case à ta
C#: 
public class MinStack {

    List<int> stack;
    /** initialize your data structure here. */
    public MinStack() {
       stack  = new List<int>();
    }
    
    public void Push(int x) {
        stack.Add(x);
    }
    
    public void Pop() {
        stack.RemoveAt(stack.Count - 1);
    }
    
    public int Top() {
        return stack[stack.Count - 1];
    }
    
    public int GetMin() {
        return stack.Min();
    }
}
 
Đúng là chỉ có 1 test case!

Java: 
class MinStack {

    List<Integer> stack;
    
    public MinStack() {
        stack = new ArrayList<>();
    }
    
    public void push(int x) {
        stack.add(x);
    }
    
    public void pop() {
        stack.remove(stack.size() - 1);
    }
    
    public int top() {
        return stack.get(stack.size() - 1);
    }
    
    public int getMin() {
        return Collections.min(stack);
    }
}
 
Mấy bác trên giải kiểu gì vậy nhỉ? O(1) tất cả các thao tác mà dùng Collections.min với List.min.

chaungoan said:
Code: 
class MinStack {
private:
    vector<int> results;
    vector<int> min_;
public:
    /** initialize your data structure here. */
   
    MinStack() {
       
    }
   
    void push(int x) {
        results.push_back(x);
        if (min_.size() == 0 || x < min_.back()) min_.push_back(x);
        else (min_.push_back(min_.back()));
    }
   
    void pop() {
        results.pop_back();
        min_.pop_back();
    }
   
    int top() {
        return results.back();
    }
   
    int getMin() {
        return min_.back();
    }
};
Click to expand...

Đọc chưa hiểu hàm push của bác này lắm. Add vào stack số x mà cái min lại biến đổi như này?
min_.push_back(min_.back())
 

Similar threads

Zuytori
Tiếp nhận đơn xin khai thác 'kho báu' 3 tấn vàng dưới lòng sông ở Bình Thuận
Replies
8
Views
473
yokitonara
Y
Nobitadiradivo
Phê duyệt gần 14.000 tỷ đầu tư tuyến đường nối cao tốc Biên Hòa – Vũng Tàu
Replies
4
Views
369
TraChanhMuoiMe
TraChanhMuoiMe
BaryonicLord
Tính toán kịch bản đánh thuế tiêu thụ đặc biệt, đảo ngược xu hướng tiêu thụ đồ uống có đường
2 3
Replies
47
Views
3K
Cún Xjnh
Cún Xjnh
sankhaukich
Nước cống đen kịt xả ra vịnh Hạ Long
4 5 6
Replies
103
Views
8K
Han sara
Han sara
N
thắc mắc Tìm phim trộm vàng
Replies
2
Views
111
nottelling
N

Share this page

Back
Top