Thám hiểm sao Mộc

View as PDF

Submit solution

Points: 1.11 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
by winterwolf94
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Sau nhiều năm trời rong ruổi trên nước Mỹ, Trung đã trở thành một chuyên gia hàng đầu trong lĩnh vực Robot và làm việc cho NASA. Năm ~2030~ có một dự án hợp tác giữa Mỹ và Việt Nam hứa hẹn sẽ đưa ngành công nghiệp vũ trụ thế giới lên một tầm cao mới: đưa robot thăm dò địa chất lên sao Mộc. Do là kỹ sư hàng đầu, Trung được giao cho việc lập trình hệ thống điều khiển của Robot.

Ngày trọng đại đã đến: Robot LEGO được phi thuyền SSO đưa vào vũ trụ và hạ cánh trên sao Mộc. LEGO được dự tính sẽ hạ cánh trên một mỏ quặng nhưng do có sai sót nhỏ trong quá trình tính toán, SSO đưa LEGO đến một địa điểm khác. Trên Trái đất, Trung có nhiệm vụ truyền lệnh để LEGO đến được mỏ quặng. Một dãy lệnh ~S~ là một dãy các số nguyên ~S_{i}~ với độ dài ~L~. Khi LEGO nhận được dãy ~S~, bộ giải mã sẽ bắt đầu đọc theo thứ tự ~S_{1}~, ~S_{2}~, ~S_{3}~, ..., ~S_{L}~. Khi gặp số nguyên ~S_{i}~, nếu

  • ~S_{i} > 0~: LEGO di chuyển về phía trước ~S_{i}~ bước
  • ~S_{i} = 0~: LEGO quay sang trái ~90^{0}~
  • ~S_{i} = - 1~: LEGO quay sang phải ~90^{0}~
  • ~S_{i} < - 1~: LEGO đi lùi về phía sau ~(-S_{i} - 1)~ bước (hướng trước mặt vẫn không đổi)

Điều khiển LEGO tới mở quặng là một chuyện hết sức đơn giản với Trung. Tuy nhiên do là cựu học sinh chuyên Tin, Trung hứng thú với một câu hỏi vừa nảy ra trong đầu: có bao nhiêu dãy lệnh điều khiển khác nhau gồm ít lệnh nhất để LEGO đến được mỏ quặng? Hai dãy lệnh điều khiển ~S~ và ~T~ độ dài ~L~ được xem là khác nhau nếu tồn tại một vị trí ~i \le L~ sao cho ~S_{i} \neq T_{i}~. Trung chỉ cần điều khiển LEGO di chuyển đến mỏ quặng, hướng của nó không quan trọng.

LEGO có một camera hồng ngoại ghi lại địa hình khu vực xung quanh. Hình ảnh này được truyền về Trái đất dưới dạng một bản đồ hình chữ nhật kích thước ~M \times N~ (miêu tả trong input). LEGO chỉ di chuyển được trên địa hình bằng phẳng. Mỗi bước di chuyển LEGO có thể đi đến ô ngay phía trước hoặc phía sau hướng nó đang quay mặt tới.

Input

Dòng đầu tiên là ~2~ số nguyên dương ~M~, ~N~ ~(1 \le M~, ~N \le 200)~

~M~ dòng sau, dòng thứ ~i~ gồm ~N~ kí tự ~A[i~, ~j]~ thể hiện bản đồ. ~A[i~, ~j]~ có thể là:

  • '.': địa hình bằng phẳng
  • '*': địa hình gồ ghề, hiểm trở
  • 'X': vị trí mỏ quặng. Có duy nhất một mỏ.
  • 'E', 'W', 'S' hoặc 'N': vị trí hiện tại và hướng trước mặt của LEGO (tương ứng với Đông, Tây, Nam, Bắc).

Output

Gồm ~2~ số nguyên dương là ~L~ -- độ dài dãy lệnh ngắn nhất và ~K~ -- số dãy lệnh khác nhau có cùng độ dài ~L~ có thể đưa LEGO đến mỏ quặng. Nếu không tồn tại đường đi xem như ~L = K = 0~.

Sample Input

6 5
....X
.***.
.***.
.***.
.***.
N....

Sample Output

3 2

Note

Có ~2~ dãy lệnh là ~5~ ~-1~ ~4~ và ~5~ ~0~ ~-5~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.