Loang

Cho trước bản đồ của một tòa nhà, và nhiệm vụ của bạn là đếm số lượng phòng của nó. Kích thước của bản đồ là \(n \times m\) hình vuông, và mỗi hình vuông là sàn hoặc tường. Bạn có thể đi bộ sang trái, phải, lên trên và xuống dưới qua các ô sàn nhà.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): kích thước của bản đồ
• \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) ký tự mô tả bản đồ. Mỗi ký tự là . (sàn) hoặc # (tường)
• Ràng buộc:
  • \(1 \leq n, m \leq 1000\)

Output

• In một số nguyên: số lượng phòng

Example

5 8
########
#..#...#
####.#.#
#..#...#
########

3

Cho bản đồ của một mê cung, nhiệm vụ của bạn là tìm ra một đường đi từ vị trí bắt đầu đến vị trí kết thúc. Bạn có thể đi sang trái, phải, lên trên và xuống dưới.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): chiều cao và chiều rộng của bản đồ
• \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) ký tự mô tả mê cung. Mỗi ký tự là . (sàn), # (tường), A (bắt đầu) hoặc B (kết thúc)

Output

• Đầu tiên in YES nếu tồn tại đường đi và NO nếu ngược lại
• Nếu có đường đi, dòng tiếp theo in độ dài của đường đi ngắn nhất
• Dòng cuối in mô tả của đường đi đó dưới dạng một xâu bao gồm các ký tự L (trái), R (phải), U (lên) và D (xuống). Bạn có thể in bất kỳ giải pháp hợp lệ nào

Constraints

• \(1 \leq n, m \leq 1000\)

Example

5 8
########
#.A#...#
#.##.#B#
#......#
########

YES
9
LDDRRRRRU

Nông trang có rất nhiều ngọn đồi núi, để bảo vệ nông trang nông dân John muốn đặt người canh gác trên các ngọn đồi này. Anh ta băn khoăn không biết sẽ cần bao nhiêu người canh gác nếu như anh ta muốn đặt 1 người canh gác trên đỉnh của mỗi đồi. Anh ta có bản đồ của nông trang là một ma trận gồm \(N (1 < N \leq 700)\) hàng và \(M (1 \leq M \leq 700)\) cột. Mỗi phần tử của ma trận là độ cao \(H_{ij}\) so với mặt nước biển \((0 \leq H_{ij} \leq 10000)\) của ô \((i,j)\). Hãy giúp anh ta xác định số lượng đỉnh đồi trên bản đồ.

Đỉnh đồi là \(1\) hoặc nhiều ô nằm kề nhau của ma trận có cùng độ cao được bao quanh bởi cạnh của bản đồ hoặc bởi các ô có độ cao nhỏ hơn. Hai ô gọi là kề nhau nếu độ chênh lệch giữa tọa độ \(X\) không quá \(1\) và chênh lệch tọa độ \(Y\) không quá \(1\).

Input

• Dòng 1: Hai số nguyên cách nhau bởi dấu cách: \(N\) và \(M\)
• Dòng 2 \(\ldots\) N + 1: Dòng \(i+1\) mô tả hàng \(i\) của ma trận với \(M\) số nguyên cách nhau bởi dấu cách: \(H_{ij}\)

Output

• Một số nguyên duy nhất là số lượng đỉnh đồi.

Example

8 7
4 3 2 2 1 0 1
3 3 3 2 1 0 1
2 2 2 2 1 0 0    
2 1 1 1 1 0 0
1 1 0 0 0 1 0
0 0 0 1 1 1 0
0 1 2 2 1 1 0
0 1 1 1 2 1 0 

3

Vua Arthur và các hiệp sĩ bàn tròn thường gặp nhau vào đầu năm mới để ăn mừng tình bạn của họ. Để tưởng nhớ sự kiện này, chúng ta xem xét một trò chơi, trong đó có một quân vua và một vài quân mã được đặt ngẫu nhiên trên các ô riêng biệt. Bàn cờ có kích thước \(n × n\), trên bàn cờ có một số ô cấm những ô còn lại là những ô tự do – ô có thể di chuyển vào được. Các ô đặt quân mã và quân vua đang đứng ở các ô tự do.

Tại mỗi bước tất cả các quân đều phải di chuyển theo quy tắc và không được đi vào ô cấm, hãy tìm cách di chuyển để chúng gặp nhau nhanh nhất.

Input

• Dòng đầu là số \(n\);
• \(n\) dòng tiếp theo, mỗi dòng 1 xâu \(n\) ký tự, gồm các ký tự . thể hiện ô trống, # thể hiện ô cấm không được phép đi vào, T thể hiện vị trí vua đang đứng, M thể hiện vị trí quân mã đang đứng.

Output

• Gồm một số là số bước ít nhất để các quân gặp nhau, nếu không thể gặp được nhau ghi \(-1\).

Scoring

• Subtask \(1\): \(n ≤ 20\) và chỉ có một quân mã;
• Subtask \(2\): \(n ≤ 100\) và chỉ có một quân mã;
• Subtask \(3\): \(n ≤ 100\).

Example

5
M....
.....
.#...
.#..#
...#T

2