Giải bài trực tuyến

Cho bảng N x N (N ≤ 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.

Dữ liệu vào:

• Dòng đầu tiên chứa số N (1 ≤ N ≤ 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. 

Dữ liệu ra:

• 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.

Lưu ý:

Có 40% số test có N ≤ 4

Ví dụ:

Input:
3
110 
001
100

Output:
4

Giải thích: 4 phép touch cần dùng ở vị trí (1,1), (1,2), (1,3), (2,1).