Nội dung Bài tập
Mã:
GALAXYCARRACE
Tên:
Cuộc đua xuyên Ngân Hà
Dạng thi:
oi
Thang điểm:
10 điểm
Giới hạn thời gian:
1 giây
Giới hạn bộ nhớ:
256 MB
Được tạo bởi:
4801104085
DORAEMON VÀ CUỘC ĐUA XUYÊN NGÂN HÀ (ngoại truyện :> )
Doraemon cùng Nobita và những người bạn của mình tham gia vào một cuộc đua để có cho mình phần thưởng là một điều ước theo ý muốn. Trong khi các bạn khác cùng với những đội đối thủ đáng gờm có những loại xe đua cùng với những tính năng ưu việt giúp tăng tỉ lệ về đích đầu tiên, thì Doraemon cùng Nobita có cho mình là một chiếc xe "xe đạp vịt" :) .

Mặc dù chiếc xe có tốc độ đáng kinh ngạc, song do phải sử dụng bằng năng lượng chạy bằng cơm nên Nobita nhờ Doraemon cần tìm con đường ngắn nhất đến cổng không gian tiếp theo để có thể đỡ chút sức lực trong các chặng tiếp theo. Nhưng do bảo bối "Cây gậy tìm đường đi" của Doraemon đang bị trục trặc chỉ sai đường nên không thể sử dụng ngay được. Nên Doraemon nhờ các bạn tạo một chương trình tìm đường đi ngắn nhất từ cổng vào không gian A đến cổng không gian tiếp theo B, các bạn hãy giúp bạn ấy nhé! Biết rằng họ đi được theo hai hướng ngang và dọc.

Input:
- Dòng đầu tiên chứa 2 số nguyên n, m là ma trận địa hình n dòng và m cột (n,m < 1001 )
- n dòng tiếp theo chứa m ký tự quy ước như sau: '.' là đường đi có thể đi được, '#' là chứng ngại vật cần tránh, 'A' và 'B' lần lượt là cổng không gian vào và ra (chỉ có duy nhất 2 cổng không gian trên)
Output:
- Dòng đầu tiên xuất ra "YES" nếu tìm được, ngược lại xuất ra "NO".
- Nếu YES thì dòng thứ hai xuất ra độ dài quãng đường ngắn nhất (tính theo 1 đơn vị)

Ví dụ 1:

Input

Output

5 8

########

#.A#...#

#.##.#B#

#......#

########

YES

9



Ví dụ 2:

Input

Output

5 8

########

#.A.####

#...#.B#

#...#..#

########

NO





    Quảng cáo
       Ngôn ngữ : 

       Theme : 
Mời bạn soạn code



		



      Ai có thể xem bài này : 

Thông tin



Phần thảo luận