Cần giúp đỡ bài tập về DFS cơ bản

Trang12 · March 4, 2019, 6:48am

Hỏi dfs cơ bản ai giỏi thuật toán giúp chứ e nghĩ 2 ngày r chưa ra

rogp10 · March 4, 2019, 10:43am

Do luôn ở dưới đất nên ta có thể dùng mảng hai chiều để mô tả trạng thái như sau: lưu vị trí của ta vào một biến và độ cao của các tảng đá (rock) vào từng dòng. VD:

1
6 2 0 0 0 0
0 0 0 0 0 0
3 1 0 0 0 0

nghĩa là ta ở cột 1 và cột 0 tảng đá sẽ rơi ở t=6 và t=2.

Trang12 · March 4, 2019, 10:36am

Ah giải thích rõ tí nữa đk k ạ

rogp10 · March 4, 2019, 10:44am

Cái này là biến đổi bài toán ta mã hóa trạng thái sao cho thời gian cập nhật là ngắn nhất có thể. Thay vì phải dò hết ma trận, ta chỉ cần dò trạng thái các tảng đá.