Đường Đi Nhỏ Nhất Trên Lưới

Điểm: 1,00 (OI)

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

Python 3 5.0s

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

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

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

Cho lưới ô vuông kích thước $n \times n$ , mỗi ô chứa một chữ cái in hoa (A-Z). Bạn đi từ ô trái trên $(1, 1)$ đến ô phải dưới $(n, n)$ , mỗi bước chỉ được đi sang phải hoặc xuống dưới. Đường đi tạo thành một xâu gồm $2 n - 1$ ký tự. Tìm xâu nhỏ nhất theo thứ tự từ điển.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $n$ .

$n$ dòng tiếp theo, mỗi dòng chứa $n$ chữ cái in hoa.

Dữ liệu ra

In ra xâu nhỏ nhất theo thứ tự từ điển.

Ràng buộc

$1 \leq n \leq 3000$

Ví dụ

Input	Output	Giải thích
10 CBCDCCDBCA DDACDDCACA DBBCDCBAAA DAABBACBDC ACDBACBBBA DDADCCCABA BCABDCABDC ADCBADCDAB CCBBBDDDCB BCDBDBDCAA	CBCABABBACBBABACBBA	Đường đi tối ưu trên lưới $10 \times 10$

Bình luận

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