Bình luận

• 
  

  2

  

  minhkochamhoc  đã bình luận lúc 30, Tháng 10, 2025, 4:08 ← sửa 15 →

  solve:

  tóm tắt đề :

  • cho 1 ma trận cỡ r * c (r , c <= 100) ban đầu ta ở vị trí S và có lượng hp = 3 ( nếu hp về 0 nhân vật sẽ hẹo ) , ta có thể di chuyển qua 4 ô kề cạnh (lên , xuống , phải , trái ) nếu đi vào 1 ô chứa kí tự '+' ta sẽ bị trừ 1 hp , còn ô '-' thì ko bị làm sao , ta cần tìm đường đi ngắn nhất để đi từ S -> D sao cho nhân vật của ta còn sống ( hp > 0) .

  hướng tiếp cận :

  • dễ thấy nếu xét đường đi ngắn nhất trên bảng ko có trọng số ta có thể nghĩ tới BFS
  • vậy còn để xử lý điều kiện thì ta thấy rằng giới hạn của r , c , hp (r , c <= 100 và hp <= 3) khá nhỏ cho nên có thể xét toàn bộ r * c * hp trường hợp xảy ra
  • do đó ta gọi MinDist[u][v][k] là số bước cần đi ít nhất để đi từ vị trí xuất phát tới ô [u][v] mà còn k hp
  • từ đó ta tiến hành BFS với việc lưu 3 biến 1 lúc là {u,v,k} để thu kết quả như sau :
  • khi xét tại vị trí ô [i][j][k] đang nằm trong danh sách BFS
  • ta sẽ xét 4 ô kề cạnh nó là [i+1][j] , [i-1][j] , [i][j+1] , [i][j-1]
  • nếu ô kề cạnh này ( gọi là ô [u][v]) chứa dấu '+' thì hp của ô này bằng hp ô đg đứng -1 , nếu hp về 0 ta bỏ qua ô này
  • còn nếu đi tới ô đó mà hp > 0 ta sẽ cập nhật MinDist[u][v][hp] = MinDist[i][j][k] + 1 và đẩy trạng thái {u,v,hp} vào BFS
  • kết quả của ta là min( MinDist[i][j][1] , MinDist[i][j][2] , MinDist[i][j][3] ) (nhớ ktra trường hợp ko tới đc D)

  • code của tớ : hehehe
  • mình biết mình viết lời giải này chưa tốt nhưng mong rằng có thể phần nào đó giúp đỡ những bạn ms học trên con đường lập trình thi đấu này