JOI 2014 - JOI Emblem

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Dạng bài
Ngôn ngữ cho phép
Assembly, Awk, C, C#, C++, Clang, Cobol, D, Groovy, Haskell, JS, Java, Kotlin, Lua, Node JS, OCaml, ObjectiveC, PHP, Pascal, Perl, Prolog, Pypy, Pypy 3, Python, Ruby, Rust, Scala, Scratch, Swift
Điểm: 1100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Ủy ban Olympic Tin học Nhật Bản quyết định làm một lá cờ JOI mới để cổ vũ các thí sinh tham dự kỳ thi tại Đài Loan.

Lá cờ JOI gồm các ô vuông xếp thành \(M\) hàng và \(N\) cột. Mỗi ô vuông chứa đúng một trong ba chữ cái J, O, I.

Ngoài lá cờ JOI, ủy ban còn quy định một huy hiệu JOI. Huy hiệu gồm các ô vuông xếp thành \(2\) hàng và \(2\) cột, mỗi ô chứa đúng một trong ba chữ cái J, O, I.

Số huy hiệu JOI có trong một lá cờ là số vùng gồm \(2\) hàng liên tiếp và \(2\) cột liên tiếp mà cách sắp xếp các chữ cái trùng với huy hiệu JOI, không xoay hay lật. Các vùng thỏa mãn được đếm riêng, kể cả khi chúng chồng lên nhau.

Ủy ban có một lá cờ JOI cũ và một mảnh giấy trắng có kích thước bằng một ô vuông của lá cờ. Có thể viết lên mảnh giấy một chữ cái tùy chọn trong J, O, I. Để tạo lá cờ mới, ủy ban sẽ thực hiện một trong hai cách sau:

  • Giữ nguyên lá cờ cũ làm lá cờ mới, không dùng mảnh giấy.
  • Viết một chữ cái lên mảnh giấy rồi dán đè lên một ô vuông bất kỳ của lá cờ cũ, thay đổi đúng một vị trí. Lá cờ sau khi thay đổi là lá cờ mới.

Ủy ban muốn số huy hiệu JOI có trong lá cờ mới lớn nhất có thể.

Yêu cầu

Cho thông tin về lá cờ JOI cũ và huy hiệu JOI, hãy tính số huy hiệu JOI lớn nhất có thể có trong lá cờ mới.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

  • Dòng đầu chứa hai số nguyên \(M, N\) cách nhau bởi một dấu cách, cho biết lá cờ có \(M\) hàng và \(N\) cột.
  • Mỗi dòng trong \(M\) dòng tiếp theo chứa một xâu gồm \(N\) chữ cái J, O, I. Ký tự thứ \(j\) từ trái sang của dòng thứ \(i\) trong các dòng này là chữ cái ở hàng \(i\) từ trên xuống, cột \(j\) từ trái sang của lá cờ cũ, với \(1 \le i \le M\), \(1 \le j \le N\).
  • Mỗi dòng trong \(2\) dòng tiếp theo chứa một xâu gồm \(2\) chữ cái J, O, I. Ký tự thứ \(j\) từ trái sang của dòng thứ \(i\) trong hai dòng này là chữ cái ở hàng \(i\) từ trên xuống, cột \(j\) từ trái sang của huy hiệu JOI, với \(1 \le i,j \le 2\).

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên: số huy hiệu JOI lớn nhất có thể có trong lá cờ mới.

Ràng buộc

  • \(2 \le M \le 1\,000\).
  • \(2 \le N \le 1\,000\).

Phân nhóm

  • Nhóm 1 (30 điểm): \(M \le 50\), \(N \le 50\).
  • Nhóm 2 (70 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
3 5
JOIJO
IJOOO
IIJIJ
JO
IJ
Output 
3
Giải thích

Lá cờ cũ và huy hiệu JOI giống các ví dụ trong hình minh họa ở phần mô tả. Nếu dùng mảnh giấy đổi ô ở hàng \(2\) từ trên xuống, cột \(4\) từ trái sang thành J, ta được lá cờ như trong hình minh họa việc thay đổi một vị trí.

Sau thay đổi này, lá cờ có \(3\) vùng với cách sắp xếp giống huy hiệu JOI, được chỉ ra trong hình sau.

Không có cách tạo lá cờ mới chứa từ \(4\) vùng như vậy trở lên, nên đáp án là \(3\).

Ví dụ 2

Input 
2 6
JOJOJO
OJOJOJ
OJ
JO
Output 
2
Giải thích

Lưu ý rằng có trường hợp đạt được giá trị lớn nhất mà không cần dùng mảnh giấy trắng.

Ví dụ 3

Input 
2 2
JI
IJ
JJ
JJ
Output 
0
Giải thích

Trong ví dụ này, mọi lá cờ mới có thể tạo ra đều không chứa huy hiệu JOI nào.

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.

Kỳ thi: