30/09/2018, 16:16
Cho mình xin ý tưởng về truy vết trong bảng
Mình đang làm một bài dùng đệ quy để tìm đường từ vị trí A đến vị trí B trên một bảng NxM. Ai cho mình xin ý tưởng chung về truy vết với…
Bài liên quan
Bài toán ma trận hay sao vậy @Rok_Hoang? Mà thể loại này học lâu rồi, :running: thôi =))
kiểu như bài tìm đường đi trong đồ thị ý nhỉ
tìm đường đi trong đồ thị ấy, một ô đi được 4 hướng, nhưng không biết lưu vết thế nào đây
@Rok_Hoang cho cái đề cụ thể hơn 1 tí đi. Đồ thị đó có cấu trúc như thế nào nữa chứ.
một bảng có kích thước NxM,mỗi ô sẽ có giá trị 1 hoặc 0, nếu 1 thì mình được đi trên ô đó, từ một ô có thể đi 4 hướng (lên xuống trái phải), cho 2 tọa độ A và B. . tìm đường đi từ A đến B.
Chưa học đến đồ thị nhưng kiểu lưu đường đi trên ma trận thì chắc là dùng thêm 1 ma trận cùng kích cỡ để lưu hướng đi tại tọa độ (i,j). Giả sử cho 4 giá trị 1,2,3,4 đặc trưng cho 4 hướng lên, xuống, trái, phải chẳng hạn. Nếu đến tọa độ (i,j) nào đó mà không đi được tiếp nữa thì gán cho giá trị INT_MAX cũng được.
nếu có nhiều đường đi thì mình lưu như thế nào ?
Nếu có nhiều đường đi thì dùng stack lưu lại.