Bảng ô vuông

View as PDF

Submit solution


Points: 0.36 (partial)
Time limit: 0.6s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
virtuspro94 - Sưu tầm
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho bảng ~N \times N~ ~(N \leq 14)~. Mỗi ô là ~1~ số ~0~ hoặc ~1~. Một phép ~Touch(i, j)~ cho phép đổi ngược giá trị của ô ~(i, j)~ ~-~ hàng ~i~, cột ~j -~ và các ô kề cạnh (nếu có) từ ~0~ thành ~1~ và từ ~1~ thành ~0~. Trạng thái đích là trạng thái mà cả bảng đều là ~0~ hoặc đều là ~1~.

Yêu cầu: Tìm số bước ít nhất để đến được trạng thái đích. Nếu ko có cách nào in ra ~- 1~.

Input

  • Dòng đầu tiên chứa số ~N~ ~(1 \leq N \leq 14)~.
  • ~N~ dòng tiếp theo, mỗi dòng chứa ~N~ kí tự '0' hoặc '1' mô tả trạng thái của bảng.

Output

  • ~1~ số duy nhất là số bước ít nhất để đến được trạng thái đích. Nếu ko có cách nào in ra ~- 1~.

Giới hạn

Có ~40\%~ số test có ~N \leq 4~

Sample Input

3
110
001
100

Sample Output

4

Note

~4~ phép touch cần dùng ở vị trí ~(1, 1), (1, 2), (1, 3), (2, 1)~.


Comments

Please read the guidelines before commenting.


There are no comments at the moment.