trang chủ / đề bài / icpcwf25_d

Xe tự hành lỗi

Đề bài

Mô tả

Trung tâm Bản đồ Hành tinh Quốc tế (ICPC) dùng các xe tự hành để khám phá bề mặt của những hành tinh khác. Như ai cũng biết, các hành tinh khác là những mặt phẳng có thể được chia đều và hoàn hảo thành một lưới hình chữ nhật. Mỗi ô của lưới hoặc bằng phẳng và xe có thể đi vào, hoặc là đá và xe không thể đi vào.

Hôm nay là ngày ra mắt chiếc xe tự hành Hornet hoàn toàn mới. Xe sẽ khám phá hành tinh theo một thuật toán đơn giản. Bên trong, xe lưu một thứ tự hướng, là một hoán vị của bốn hướng bắc, đông, nam và tây. Khi thực hiện một bước di chuyển, xe duyệt thứ tự hướng của mình, chọn hướng đầu tiên mà khi đi theo hướng đó xe không rơi ra khỏi bề mặt hành tinh và không đi vào ô đá, rồi đi một bước theo hướng đó.

Giữa hai bước di chuyển liên tiếp, xe có thể bị một tia vũ trụ chiếu trúng, khiến thứ tự hướng của xe bị thay bằng một thứ tự khác. Các nhà khoa học của ICPC có nhật ký các bước di chuyển của xe, nhưng rất khó để xác định bằng tay xem thứ tự hướng có thay đổi hay không và thay đổi khi nào. Cho các bước di chuyển mà xe đã thực hiện, hỏi số lần ít nhất mà xe có thể đã bị tia vũ trụ chiếu trúng là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên r và c (1≤r≤200, 1≤c≤200), trong đó r là số hàng và c là số cột của hành tinh. Các hàng được đánh từ bắc xuống nam, các cột được đánh từ tây sang đông.

Mỗi dòng trong r dòng tiếp theo chứa c ký tự mô tả bề mặt hành tinh. Mỗi ký tự là # (ô đá), . (ô bằng phẳng) hoặc S (ô bằng phẳng, là vị trí xuất phát của xe). Lưới có đúng một ký tự S.

Dòng cuối cùng chứa xâu s, mỗi ký tự của s là N (bắc), E (đông), S (nam) hoặc W (tây), mô tả dãy các bước di chuyển mà xe đã thực hiện. Xâu s có từ 1 đến 10000 ký tự. Mọi bước di chuyển đều đi vào ô bằng phẳng.

Dữ liệu ra

In ra số lần ít nhất mà thứ tự hướng của xe có thể đã thay đổi sao cho phù hợp với các bước di chuyển của xe.

Ràng buộc

  • 1≤r,c≤200.
  • 1≤|s|≤10000.
  • Lưới có đúng một ô S; mọi bước di chuyển đều nằm trong lưới và đi vào ô không phải đá.

Ví dụ

Input Output Giải thích
5 3
#..
...
...
...
.S.
NNEN
1 Ở bước 1, xe hoặc ưu tiên hướng bắc, hoặc ưu tiên nam rồi đến bắc (không thể đi về nam vì sẽ rơi khỏi hành tinh). Ở bước 2 xe phải ưu tiên bắc, ở bước 3 phải ưu tiên đông. Ở bước 4 xe ưu tiên bắc, hoặc đông rồi đến bắc. Vậy có thể xe bị chiếu trúng đúng một lần giữa bước 2 và bước 3, thứ tự hướng đổi từ N??? thành EN?? (dấu ? là một hướng bất kỳ còn lại).
3 5
.###.
....#
.S...
NEESNS
0 Có thể xe bắt đầu với thứ tự hướng NESW, phù hợp với mọi bước di chuyển.
3 3
...
...
S#.
NEESNNWWSENESS
4 Không có cách chia dãy bước thành ít hơn 5 đoạn liên tiếp mà mỗi đoạn được thực hiện bởi cùng một thứ tự hướng.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0