Hành trình vượt thời gian

View as PDF

Submit solution

Points: 0.18 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Vì học dốt, bạn bị nhốt vào một mê cung kích thước M*N, được chia thành các ô vuông ~1*1~. Bạn phải di chuyển từ điểm ~S~ đến điểm ~T~. Một số ô trên mê cung là tường, và bạn không thể di chuyển vào được.

Có thể không tồn tại đường đi trên mê cung thỏa mãn đề bài. Tuy nhiên, bạn có trong tay một cỗ máy thời gian. Khi gặp vật cản, nếu trong quá khứ vật cản này không tồn tại, bạn có thể quay ngược thời gian về thời điểm đó, di chuyển qua vật cản, rồi quay trở lại thời điểm hiện tại (nếu cần), tiếp tục di chuyển... Vì việc đảo ngược thời gian là vô cùng nguy hiểm, bạn quyết định chỉ di chuyển giữa thời điểm hiện tại và một thời điểm duy nhất trong quá khứ. Và bạn cũng cố gắng chỉ di chuyển số lần ít nhất.

Bạn biết trước bản đồ của mê cung tại thời điểm hiện tại và thời điểm trong quá khứ (mà bạn sẽ di chuyển về), hãy tìm số lần di chuyển ít nhất có thể.

Chú ý: Nếu trước khi thay đổi thời gian, bạn ở ô hàng ~i~, cột ~j~, thì sau khi thay đổi thời gian, bạn vẫn ở ô hàng ~i~, cột ~j~. Như vậy, bạn chỉ có thể sử dụng máy thời gian ở ô hàng ~i~, cột ~j~, nếu ô tương ứng ở cả hiện tại và quá khứ đều là ô trống.

Input

Dòng đầu tiên ghi 2 số nguyên dương ~M~, ~N~ ~(1 \le M, N \le 1000)~. ~M~ dòng tiếp theo, mỗi dòng gồm ~N~ ký tự, mô tả mê cung ở thời điểm hiện tại. Mỗi ký tự có thể là:

  • '.' nếu ô tương ứng là ô trống
  • '#' nếu ô tương ứng có chướng ngại vật và không thể đi vào được
  • 'S' nếu ô tương ứng là ô xuất phát
  • 'T' nếu ô tương ứng là ô đích

~M~ dòng tiếp theo, mỗi dòng gồm ~N~ ký tự mô tả mê cung tại thời điểm quá khứ, với định dạng tương tự. Có duy nhất một ô ~S~ và một ô ~T~ trong mê cung ở thời điểm hiện tại. Không có ô ~S~ và ô ~T~ trong mê cung ở thời điểm quá khứ.

Output

Gồm một số nguyên dương duy nhất là số lần sử dụng cỗ máy thời gian ít nhất

Sample Input 1

3 3
S..
###
..T
...
...
...

Sample Output 1

2

Sample Input 2

2 2
S.
.T
..
#.

Sample Output 2

0

Comments

Please read the guidelines before commenting.


There are no comments at the moment.