📖 Bài giảng & lời giải: đây là Bài tập 7 trong bài giảng Thuật toán qua trò chơi 5: Cờ caro trên blog Lập trình thuật toán – có lý thuyết, mô phỏng từng bước, gợi ý và code C++ / Python.

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới xem gợi ý và lời giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Cho bàn caro $n \times m$ (ký tự X, O, .). Xét lần lượt bốn hướng: ngang, dọc, chéo chính (xuống phải) và chéo phụ (xuống trái). Theo mỗi hướng, bàn cờ được chia thành các chuỗi tối đa: dãy các quân cùng màu nằm liên tiếp theo hướng đó, không thể kéo dài thêm về hai phía (một quân đứng riêng cũng là một chuỗi độ dài 1, và mỗi quân thuộc đúng một chuỗi theo mỗi hướng).

Một chuỗi độ dài $L$ được chấm điểm như sau. Gọi đầu mở là ô ngay trước quân đầu tiên hoặc ngay sau quân cuối cùng của chuỗi (theo hướng đó) mà nằm trong bàn và là ô trống ..

• Nếu $L \ge 5$: được $100000$ điểm.
• Ngược lại, nếu cả hai đầu đều mở: được $10^L$ điểm; nếu đúng một đầu mở: được $10^{L-1}$ điểm; nếu không đầu nào mở: được $0$ điểm.

Điểm của một người là tổng điểm của mọi chuỗi quân của người đó theo cả bốn hướng. Hãy in điểm của X và điểm của O.

Dữ liệu vào

• Dòng 1: hai số nguyên $n, m$ ($1 \le n, m \le 200$).
• $n$ dòng tiếp theo, mỗi dòng là một xâu độ dài $m$ chỉ gồm X, O, ..

Kết quả

In ra hai số nguyên: tổng điểm của X và tổng điểm của O, cách nhau một dấu cách.

Sample Input

3 6
......
.XXX..
.O..O.

Sample Output

1063 23