COCI 2020/2021 - Contest 4 - Patkice II

View as PDF

Submit solution

Points: 1.70 (partial)
Time limit: 2.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 4
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Sau khi Hollywood đã thành công trong câu chuyện về cuộc phiêu lưu trên biển của chiếc ô giữa 2 hòn đảo, Netflix quyết định sẽ thực hiện cho mình chuỗi câu chuyện về cuộc phiêu lưu của 3 chú vịt.

Các bạn chắc hẳn còn nhớ ở vòng đầu tiên của COCI 20/21, những chú vịt có bản đồ dòng biển. Những chú vịt phiêu lưu cùng nhau. Hòn đảo bắt đầu nơi mà những chú vịt sống được kí hiệu bằng kí tự o. Những chú vịt có thể bắt đầu chuyến phiêu lưu nhờ dòng biển. Dòng biển di chuyển theo 1 trong 4 hướng và được chỉ hướng bằng những kí tự: > từ Tây sang Đông, < từ Đông sang Tây, v từ Bắc xuống Nam, ^ từ Nam lên Bắc. Khi những chú vịt ở trong vùng biển này chúng sẽ phải di chuyển theo chiều của dòng biển sang ô khác.

Vùng biển tĩnh lặng được kí hiệu bằng .. Hành trình sẽ kết thúc khi những chú vịt được dòng biển đưa tới nơi biển lặng, ngoài bảng đồ hoặc quay trở về hòn đảo bắt đầu. Hòn đảo đích nơi mà những chú vịt muốn thăm được kí hiệu bởi kí tự x.

Để làm cho chuỗi câu chuyện được thú vị hơn, Netflix đã thay đổi câu chuyện. Vùng biển giờ đây còn có những vòng xoáy (những chú vịt sẽ kẹt trong 1 chu kỳ) và dòng biển có thể đưa những chú vịt ra khỏi bản đồ.

Chính vì vậy, bản đồ gốc đã bị thay đổi. Tuy nhiên với áp lực công việc cao, nhà biên tập đã phạm lỗi khiến cho các chú vịt không thể đi đến hòn đảo đích bằng những dòng biển từ hòn đảo bắt đầu của mình.

Nhà biên tập rất bận rộn. Bạn hãy giúp ông ta khắc phục bằng cách thay đổi ít kí tự nhất trên bản đồ sao cho những chú vịt có thể đi từ hòn đảo bắt đầu đến hòn đảo đích.

Vì lý do cốt truyện nên ô chứa kí tự x hoặc okhông thể thay đổi. Mọi ô còn lại đều thuộc tập kí tự <>^v. và có thể được thay thế bằng các kí tự khác cùng tập kí tự <>^v.

Input

Dòng đầu tiên chứa 2 số nguyên ~r~ và ~s~ ~(3 \leq r,s \leq 2000)~ lần lượt là số dòng và số cột trên bảng đồ.

~r~ dòng tiếp theo mỗi dòng gồm ~s~ kí tự trong tập o<>^v.x mô tả bản đồ của dòng biển.

Dữ liệu vào đảm bảo chỉ có 1 hòn đảo bắt đầu o và 1 hòn đảo đích x trên bản đồ và chúng sẽ không nằm kề nhau.

Output

Dòng đầu tiên ghi ra số nguyên ~k~ là số kí tự cần thay đổi.

~r~ dòng tiếp theo mỗi dòng gồm ~s~ kí tự mô tả bản đồ đã được sửa theo yêu cầu bài toán.

Nếu có nhiều bản đồ thỏa mãn, chỉ cần in ra 1 trong số chúng.

Sample 1

Input
3 3
>vo
vv>
x>>
Output
1
>vo
vv>
x<>

Sample 2

Input
3 6
>>vv<<
^ovvx^
^<<>>^
Output
2
>>vv<<
^o>>x^
^<<>>^

Sample 3

Input
4 4
x.v.
.>.<
>.<.
.^.o
Output
4
x<<.
.>^<
>.<^
.^.o

Subtask

  • ~5~ test đầu tiên có ~(3 \leq r,s \leq 20)~.
  • ~6~ test còn lại không ràng buộc gì thêm.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.