Thành phố liên thông mạnh

Điểm: 4,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Một thành phố có $n$ con đường nằm ngang (đông–tây) cắt $m$ con đường thẳng đứng (bắc–nam), tạo thành một lưới giao lộ $n \times m$ . Để cải thiện giao thông, thị trưởng quyết định biến mọi con đường thành đường một chiều.

Mỗi đường ngang đi theo một trong hai hướng: chỉ từ tây sang đông, hoặc chỉ từ đông sang tây.
Mỗi đường dọc đi theo một trong hai hướng: chỉ từ bắc xuống nam, hoặc chỉ từ nam lên bắc.

Tại mỗi giao lộ, có thể chuyển từ đường ngang sang đường dọc hoặc ngược lại.

Cho cấu hình hướng các con đường, hãy kiểm tra xem từ một giao lộ bất kỳ có thể đi đến mọi giao lộ khác hay không (tức là đồ thị có hướng tạo bởi các đoạn đường có liên thông mạnh hay không).

Dữ liệu vào

Dòng đầu chứa hai số nguyên $n$ và $m$ .
Dòng thứ hai chứa một xâu độ dài $n$ gồm các ký tự < và >, biểu diễn hướng các đường ngang (liệt kê từ bắc xuống nam). Ký tự thứ $i$ bằng < nghĩa là đường ngang thứ $i$ đi từ đông sang tây, bằng > nghĩa là đi từ tây sang đông.
Dòng thứ ba chứa một xâu độ dài $m$ gồm các ký tự ^ và v, biểu diễn hướng các đường dọc (liệt kê từ tây sang đông). Ký tự thứ $j$ bằng ^ nghĩa là đường dọc thứ $j$ đi từ nam lên bắc, bằng v nghĩa là đi từ bắc xuống nam.

Dữ liệu ra

In ra YES nếu từ giao lộ bất kỳ có thể đi đến mọi giao lộ khác, ngược lại in ra NO.

Ràng buộc

$2 \leq n, m \leq 20$

Ví dụ

Input	Output	Giải thích
3 3 ><> v^v	NO	Có những giao lộ không thể đi đến lẫn nhau (ví dụ giao lộ góc dưới-trái không có cạnh đi ra).
4 6 <><> v^v^v^	YES	Các hướng đường tạo thành một mạng liên thông mạnh.
2 2 <> v^	YES	Bốn giao lộ tạo thành một chu trình theo chiều kim đồng hồ.

Bình luận

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