2. JOI 2016 - Sandwich
JOI đang tham dự buổi giao lưu của IOI. Tại buổi giao lưu, những chiếc bánh sandwich được xếp trên một lưới ô vuông gồm \(R\) hàng và \(C\) cột. Mỗi chiếc bánh có dạng tam giác vuông cân với hai cạnh góc vuông có độ dài bằng cạnh của một ô. Trong mỗi ô có hai chiếc bánh được đặt sao cho hai cạnh huyền tiếp xúc với nhau. Hình dưới đây minh họa một cách xếp bánh.
Hình 1. Ví dụ về cách xếp bánh sandwich.
Không thể lấy một chiếc bánh nếu đồng thời thỏa mãn cả hai điều kiện sau:
- Cạnh huyền của nó tiếp xúc với một chiếc bánh khác chưa được lấy đi.
- Ít nhất một trong hai cạnh còn lại của nó tiếp xúc với một chiếc bánh khác chưa được lấy đi.
Mọi chiếc bánh không thỏa mãn đồng thời hai điều kiện trên đều có thể được lấy đi.
Gọi trạng thái chưa có chiếc bánh nào được lấy đi là trạng thái ban đầu. Xuất phát từ trạng thái ban đầu, để lấy một chiếc bánh nào đó, có thể cần phải lấy một số chiếc bánh khác trước. Tùy vào cách xếp bánh, cũng có thể có những chiếc bánh không thể lấy được.
JOI muốn ăn cả hai chiếc bánh nằm trong cùng một ô, nhưng chưa quyết định sẽ chọn ô nào. Cậu muốn biết, xuất phát từ trạng thái ban đầu, số chiếc bánh ít nhất phải lấy để lấy được cả hai chiếc bánh trong một ô nhất định.
Yêu cầu
Cho cách xếp bánh, hãy viết chương trình xác định với mỗi ô xem có thể lấy được cả hai chiếc bánh trong ô đó bằng cách lần lượt lấy một số chiếc bánh từ trạng thái ban đầu hay không. Nếu có thể, hãy tìm số chiếc bánh ít nhất phải lấy. Số lượng này bao gồm cả hai chiếc bánh trong ô cần lấy.
Dữ liệu vào
Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:
- Dòng đầu tiên chứa hai số nguyên \(R, C\), cách nhau bởi dấu cách, cho biết bánh được xếp trên một lưới ô vuông gồm \(R\) hàng và \(C\) cột.
- Trong \(R\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le R\)) chứa một xâu gồm \(C\) ký tự, mỗi ký tự là
NhoặcZ. Ký tự thứ \(j\) từ trái sang (\(1 \le j \le C\)) mô tả cách xếp bánh trong ô ở hàng thứ \(i\) từ trên xuống, cột thứ \(j\) từ trái sang. Hai ký tựNvàZlần lượt biểu diễn các cách xếp trong hình dưới đây.
Hình 2. Cách xếp bánh sandwich trong mỗi ô: N ở bên trái, Z ở bên phải.
Dữ liệu ra
In ra đầu ra chuẩn \(R\) dòng. Dòng thứ \(i\) (\(1 \le i \le R\)) chứa \(C\) số nguyên, cách nhau bởi dấu cách. Số thứ \(j\) (\(1 \le j \le C\)) là số chiếc bánh ít nhất phải lấy để lấy được cả hai chiếc bánh trong ô ở hàng thứ \(i\) từ trên xuống, cột thứ \(j\) từ trái sang. Nếu không thể lấy được cả hai chiếc bánh trong ô đó, in ra \(-1\).
Ràng buộc
Tất cả dữ liệu vào thỏa mãn các điều kiện sau:
Phân nhóm
- 35 điểm: \(R \le 50\) và \(C \le 50\).
- 65 điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
2 3
NZN
ZZNOutput
10 8 2
8 6 4Giải thích
Cách xếp bánh trong ví dụ 1 tương ứng với Hình 1 trong đề bài.
Chẳng hạn, để lấy cả hai chiếc bánh trong ô ở hàng thứ \(2\) từ trên xuống, cột thứ \(2\) từ trái sang, có thể lấy bánh theo thứ tự sau:
- Lấy chiếc bánh ở phía trên bên phải của ô ở hàng \(1\), cột \(3\).
- Lấy chiếc bánh ở phía dưới bên trái của ô ở hàng \(1\), cột \(3\).
- Lấy chiếc bánh ở phía trên bên phải của ô ở hàng \(2\), cột \(3\).
- Lấy chiếc bánh ở phía dưới bên trái của ô ở hàng \(2\), cột \(3\).
- Lấy chiếc bánh ở phía dưới bên phải của ô ở hàng \(2\), cột \(2\).
- Lấy chiếc bánh ở phía trên bên trái của ô ở hàng \(2\), cột \(2\).
Tổng cộng phải lấy \(6\) chiếc bánh. Đây là số lượng ít nhất, nên kết quả cho ô này là \(6\).
Ví dụ 2
Input
2 2
NZ
ZNOutput
-1 -1
-1 -1Giải thích
Trong trường hợp này, không thể lấy được bất kỳ chiếc bánh nào.
Ví dụ 3
Input
5 5
NZZZN
NNNZN
NNZNN
NZNNN
NZZZNOutput
10 12 14 16 2
8 -1 -1 -1 4
6 -1 -1 -1 6
4 -1 -1 -1 8
2 16 14 12 10