Cho một bức ảnh đen trắng kích thước 𝑚 × 𝑛 là ảnh chụp của một số sinh vật. Một sinh vật trên bức ảnh sẽ là một tập hợp các điểm đen liên thông với nhau (liên thông theo 8 hướng). Hai sinh vật được gọi là một loài nếu chúng có hình dạng giống nhau. Hai hình được gọi là giống nhau nếu sau một dãy các phép biến đổi lấy đối xứng hoặc quay 90o từ hình thứ nhất ta nhận được hình thứ hai.
Yêu cầu: Cho bảng số mô tả bức ảnh, đếm số loài trong bức ảnh.
Input :
- Dòng đầu chứa số nguyên 𝑛 (𝑛 ≤ 100);
- Dòng thứ hai chứa số nguyên 𝑚 (𝑚 ≤ 100 );
- Tiếp theo là 𝑚 dòng, mỗi là một xâu gồm 𝑛 kí tự ‘0’ hoặc ‘1’ tương ứng mô tả điểm trắng và điểm đen.
Output:
- Gồm một dòng chứa một số là số lượng loài trong bức ảnh
Input | Output |
5 6 11000 00000 00011 00001 11000 10011 |
2 |