Uolevi đã phát triển một trò chơi trong đó người chơi thu thập tiền xu trong mê cung. Hiện tại, vấn đề là trò chơi quá dễ. Bạn có thể thiết kế những mê cung đầy thử thách cho trò chơi này không?

Mỗi mê cung là một bảng ô vuông hình chữ nhật gồm các ô sàn (.) và các ô tường (#). Một ô là căn cứ (x), và một số ô có thể chứa tiền xu (o). Người chơi bắt đầu tại căn cứ và có thể di chuyển sang trái, sang phải, lên trên hoặc xuống dưới, mỗi bước sang một ô kề cạnh không phải tường và nằm trong mê cung. Nhiệm vụ của người chơi là thu thập tất cả tiền xu trong mê cung rồi quay về căn cứ.

Độ khó của một mê cung là độ dài của đường đi ngắn nhất bắt đầu tại căn cứ, thu thập tất cả tiền xu và quay về căn cứ. Độ dài được tính bằng số bước di chuyển.

Dữ liệu vào

Dữ liệu bắt đầu bằng số nguyên \(t\): số mê cung. Tiếp theo là \(t\) dòng, mỗi dòng chứa ba số nguyên \(n\), \(m\) và \(k\). Mê cung tương ứng phải có kích thước \(n \times m\) ô và chứa đúng \(k\) tiền xu.

Dữ liệu ra

In ra \(t\) mô tả mê cung theo đúng thứ tự trong dữ liệu vào, ngăn cách các mê cung bằng dòng trống. Mỗi mô tả gồm \(n\) dòng, mỗi dòng có đúng \(m\) ký tự, không có dấu cách giữa các ký tự. Chỉ được sử dụng các ký tự ., #, x và o; mỗi mê cung phải có đúng một ký tự x và đúng \(k\) ký tự o.

Mỗi mê cung phải giải được: từ căn cứ, người chơi phải có thể thu thập tất cả tiền xu rồi quay về căn cứ. Các ô sàn không chứa tiền xu có thể nằm ngoài thành phần liên thông của căn cứ.

Nộp bài

Đây là bài chỉ nộp kết quả (output-only), với duy nhất một tệp dữ liệu vào maze.in. Bạn có thể tải tệp dữ liệu vào maze.in. Bạn phải nộp một tệp kết quả maze.out chứa tất cả các mê cung được yêu cầu trong tệp dữ liệu vào.

Ràng buộc

Tệp maze.in chứa \(t=50\) mê cung. Các kích thước và số tiền xu thỏa mãn \(2 \le n,m \le 20\) và \(1 \le k \le 12\).

Chấm điểm

• Trình chấm kiểm tra kích thước, các ký tự, số căn cứ, số tiền xu và khả năng giải được của từng mê cung. Nếu bất kỳ mê cung nào không hợp lệ hoặc không giải được, toàn bộ bài nộp nhận \(0\) điểm.

• Với mỗi mê cung hợp lệ, điểm của bạn là:

  \[ \max\bigl(0,\ 100-3(d-x)\bigr), \]

  trong đó \(x\) là độ khó của mê cung bạn tạo ra, còn \(d\) là độ khó của mê cung khó nhất mà ban giám khảo tìm được cho cùng yêu cầu. Công thức này không chặn điểm ở \(100\) nếu \(x>d\).

• Tổng điểm của bài là trung bình cộng điểm của tất cả các mê cung, làm tròn xuống số nguyên:

  \[ \left\lfloor \frac{1}{t}\sum_{i=1}^{t}\max\bigl(0,\ 100-3(d_i-x_i)\bigr) \right\rfloor. \]

Ví dụ

2
3 3 1
4 7 2

###
#.x
#o#

.o.####
.#..x.#
...##.#
###o...

Nguồn

Baltic Olympiad in Informatics 2016, ngày thi thứ hai, bài B.