Xây dựng thuật toán tìm đường đi trong ma trận cho mê cung được mô tả bằng ma trận 20×20 dùng backtracking

#1

Xây dựng thuật toán tìm đường đi trong ma trận cho mê cung được mô tả bằng ma trận 20×20 dùng backtracking.

Đầu vào là ô (1,1) và đầu ra là ô (20,20)
Chỉ có thể đi ở các ô có giá trị 1 và theo hướng lên, xuống, trái và qua phải

1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 0 0 0
0 0 0 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0
0 0 1 0 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0
1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 0
1 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 1
1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 0 1
1 1 1 1 0 1 0 1 1 0 1 0 1 0 1 0 0 0 1
1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1
1 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 0 0 1
1 1 1 1 1 1 0 1 1 0 1 0 1 1 1 0 0 0 0
0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 1 1 1
1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 0 0 1
1 1 1 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 1

1 Like
#2

bạn đọc về BFS đpt O(m*n) nhé đường đi là đường ngắn nhất luôn

2 Likes
#3

Đơn giản thì cài BFS, nhanh hơn một chút dùng bi-direction BFS. Đồ thị ít chướng ngại (ô 0) thì dùng A-star.

3 Likes
#4

tưởng cài BFS mà đơn giản à, vị nào BFS rồi truy vết xem nào

#5

Thêm 1 mảng thôi mà bạn :smiley: Trace[x,y]=a* cơ_số +b; a,b là ô từ đó đi tới ô [x,y] với cơ số> mn. Trong bài này cơ số>2020

Còn mình ko biết bi-direction BFS làm sao mà nhanh hơn BFS được vậy bạn :v tưởng BFS là ngon nhất rồi :v chả lẽ còn cách cho bài này có đpt < O(mn)

#6

Mình làm được rồi nhé, cảm ơn mn. Mình dùng thêm 1 mảng để đánh dấu đường đi nữa. Mình chưa học đến phần đồ thị nên không biết làm đồ thị là j cả :sleepy:

#7

Bạn ơi, bạn có thể cho mình code bài tìm đường đi trong ma trận kia không

#8

Mình làm từ 2 tuần trk rồi, do chuyển đề tài nên cũng k kiểm tra lại
Bạn ktra lại nhé

#10

http://codepad.org/FGpt2JEx
đây nhé
file code.txt bạn tự tạo nhé :wink:

1 Like
#11

ok b. cảm ơn b nhé :v:

#12

giúp mình vs!
Ngày xửa ngày xưa, xưa ơi là xưa, xưa xửa xừa xưa, ở vương quốc “Nọ” có một chàng hiệp sĩ… nghèo. Hiệp sĩ thầm thương trộm nhớ một nàng công chúa, con của Quốc Vương. Ngày kia triều đình mở hội kén rể cho công chúa, do công chúa có thân hình mỹ miều, nhan sắc bá đạo, FA lâu năm nên điều kiện nhà vua đưa ra vô cùng đơn giản, ai đến sớm nhất là được cưới công chúa không cần sính lễ, ngoài ra còn được vua bonus thêm của hồi môn, miễn là cưới công chúa đi càng sớm càng tốt.
Hiệp sĩ vô cùng mừng rỡ và hăm hở lên đường, tuy nhiên do chàng rất nghèo chỉ có thể đi bộ nên chàng phải tìm con đường ngắn nhất để có thể đến kịp và rước được công chúa.
Bản đồ của vương quốc là một hình chữ nhật gồm m x n ô vuông (m, n < 5000), hiệp sĩ có thể đi theo bất cứ đường nào từ một ô đến các ô lân cận (ngang dọc hoặc chéo) thời gian để đi từ ô này sang ô kia là một canh giờ.
Các ô trên bản đồ được đánh tọa độ theo số dòng và số cột, ô ở góc dưới cùng bên tay trái bản đồ có tọa độ là (0, 0) và ô ở góc trên cùng bên tay phải bản đồ có tọa độ (m-1, n-1). Hiệp sĩ không được đi ra khỏi vương quốc, nếu không sẽ bị nước láng giềng tóm cổ tống giam không lấy được công chúa. Trên bản đồ có một số ô là núi cao, vực sâu, rừng thiêng nước độc không thể đi vào được. Hãy viết chương trình cho biết nếu hiệp sĩ đi suốt ngày suốt đêm không ăn không ngủ, không làm cả các “nhu cầu khác” thì phải mất bao nhiêu canh giờ hiệp sĩ mới lên được kinh đô để cưới công chúa.

INPUT
Dòng đầu tiên của input chứa 6 con số cách nhau bởi khoảng trắng, hai con số đầu lần lượt là m, n, hai số tiếp theo là tọa độ nhà của hiệp sĩ và hai con số của cùng là tọa độ của hoàng cung nơi công chúa đang mỏi mắt trông một tấm chồng.
m dòng tiếp theo trong input, mỗi dòng chứa n con số cách nhau bởi khoảng trắng. Đây là toàn bộ bản đồ vương quốc với con số 0 tượng trưng cho những ô có thể đi vào được và con số 1 tượng trưng cho những ô không thể đi vào được.

OUTPUT
Một con số duy nhất cho biết thời gian hiệp sĩ cần để đến được chỗ công chúa, tính theo canh giờ. Nếu hiệp sĩ không thể đến được chỗ công chúa xuất ra -1
input:
53 53 51 0 1 50
1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0
0 0 1 0 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 0 1
0 0 0 0 0 1 1 0 1 1 0 0 1 0 0 0 0 1 1 1 1 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 1
0 0 1 1 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1
0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 1
0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1
0 0 1 0 1 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 1 0 0 1
0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 1 0
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 1 0 1 1
0 1 1 1 0 1 0 0 1 1 0 1 1 0 0 0 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 1 0
0 1 0 0 0 1 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0
0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0
0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 1 1 1 1 0 0 1 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1
0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 0 0
0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1
1 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 0 0 1 1 0 0 1 1 0
0 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 0 0 1 0 0 0 1 1
0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0
1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 1
0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 0 0 1 0
0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0
0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 0
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 0 0 0 0 0 1 0 1 0
0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 1 0 1 1 1 0 0 0 1 0 0 1 1 0 0 0 0 0
0 0 0 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1
1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 0 1 1 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0
1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 1 1 1
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 0 1
0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 1 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 0 0
1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 0 1 1 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 0
0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 0 0 0 1 1 0 0 0 1 1
0 0 1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1
0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1
1 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 1 0 0 1
0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 1 0 1 0 1 1 0 1 0 0 0 0 1 0 0 1 1 1
1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 0 1 1
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1
1 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 1 1 1 0 1 0
1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0 1 1 1 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0
1 1 0 0 0 0 1 1 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 0 0 0
out put:59

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