Hỏi ý tưởng về truy vết trong bảng

#1

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… :smiley:

1 Like
#2

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 =))

#3

kiểu như bài tìm đường đi trong đồ thị ý nhỉ

#4

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 :frowning:

#5

@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ứ.

#6

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. :smiley:

1 Like
#7

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.

1 Like
#8

nếu có nhiều đường đi thì mình lưu như thế nào ?

#9

Nếu có nhiều đường đi thì dùng stack lưu lại.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?