TÌM ĐƯỜNG TRUNG TÂM KHẢO SÁT HANG ĐỘNG XYZ CÓ MỘT ROBOT TỰ HÀNH. ROBO...

BÀI 4: TÌM ĐƯỜNG Trung tâm khảo sát hang động XYZ có một robot tự hành. Robot này có thể tự di chuyển, vẽ sơ đồ, chụp các hình ảnh trong lòng hang động và truyền các thông tin về trung tâm. Thông tin về đường đi trong hang động được gửi về trung tâm chuỗi các chữ cái 𝐷, 𝑇, 𝑁, 𝐵 tương ứng với việc đi theo các hướng Đông, Tây, Nam, Bắc trên la bàn được gắn trên robot (trong một đơn vị khoảng cách B hướng đi không thay đổi quy chiếu trên mặt phẳng nằm ngang với mặt đất, các hướng T đi quy định ở hình bên). Trong một lần robot thực hiện nhiệm vụ khảo sát một hang D động mới, sau một thời gian di chuyển (trong quá trình di chuyển một điểm trong N hang có thể được robot đi qua, đi lại nhiều lần) và truyền thông tin về trung tâm, robot gặp sự cố và không thể di chuyển về điểm xuất phát là cửa hang. Trung tâm muốn đưa robot về cửa hang bằng cách sử dụng những đoạn đường an toàn mà robot đã đi qua một cách nhanh nhất. Yêu cầu: Cho chuỗi ký tự là thông tin đường đi của robot đã gửi về trung tâm. Hãy tìm độ dài đường đi ngắn nhất từ cửa hang đến được vị trí của robot bằng sử dụng thông tin đường đi trên. Dữ liệu vào từ tệp BAI4.INP: Một dòng gồm chuỗi các ký tự 𝐷, 𝑇, 𝑁, 𝐵 ghi liên tiếp nhau. Số ký tự không quá 10000. Kết quả ra ghi vào tệp BAI4.OUT: Độ dài đường đi ngắn nhất tìm được. Ví dụ: BAI4.INP BAI4.OUT Giải thích DDTNDBBT 4 Hình ảnh đường đi và đường đi ngắn nhất đến vị trí của robot: Lưu ý: Có 50% số test độ dài xâu nhỏ hơn hoặc bằng 1000.