connect

Bộ xử lý di động mới được phát triển Maxinos của Samsung có số lượng ô là N x N.



 


Trong 1 cell có thể có 1 lõi hoặc 1 dây dẫn điện.



 


Nguồn điện chạy dọc theo rìa Maxinos.




 

 

Dây kết nối lõi và nguồn điện chỉ có thể được lắp theo đường thẳng.



 


Các dây không thể giao nhau.




Tình trạng ban đầu của Maxinos trước khi kết nối dây được đưa ra như sau.

 

(Các Lõi ở rìa Maxinos được coi là đã được kết nối với nguồn điện.)







 

 



 

 

▶ Khi số lõi tối đa được kết nối với nguồn điện, hãy tìm tổng chiều dài của dây dẫn. 

 

   Tuy nhiên, nếu có nhiều lựa chọn khác nhau thì hãy tìm giá trị nhỏ nhất của tổng chiều dài dây dẫn.

 

 


Đáp án của bài tập trên là 12.

 

 

 

[Hạn chế]




1. 7 ≤  N ≤ 12




2. Số lượng Core lớn hơn hoặc bằng 1 và nhỏ hơn hoặc bằng 12(1 ≤   N  ≤ 12).




3. Có thể có những Lõi không được kết nối với nguồn điện, mặc dù người ta đã cố gắng kết nối nó với nguồn điện nhiều nhất có thể.

 

 

[Đầu vào]




Dòng đầu tiên chứa T, số lượng trường hợp thử nghiệm.




Các trường hợp thử nghiệm được đưa ra bắt đầu từ dòng tiếp theo.




Dòng đầu tiên của mỗi trường hợp thử nghiệm có N, và N dòng tiếp theo là điều kiện ban đầu của Maxinos , được đưa ra trong mảng N x N.




Số 0 biểu thị ô trống, số 1 biểu thị Lõi và không có số nào khác được đưa ra.

 

 


[Đầu ra]




In ' #tc ' cho mỗi trường hợp thử nghiệm và để lại một khoảng trống rồi in ra câu trả lời.




(tc đề cập đến số trường hợp thử nghiệm và bắt đầu bằng 1)




Ví dụ đầu vào

Ví dụ đầu ra

3              // Số lượng trường hợp thử nghiệm, T = 3

7          // TC 1, N = 7

0 0 1 0 0 0 0

0 0 1 0 0 0 0

0 0 0 0 0 1 0

0 0 0 0 0 0 0

1 1 0 1 0 0 0

0 1 0 0 0 0 0

0 0 0 0 0 0 0

9          // TC 2, N = 9

0 0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0 1

1 0 0 0 0 0 0 0 0

0 0 0 1 0 0 0 0 0

0 1 0 0 0 0 0 0 0

0 0 0 0 0 0 1 0 0

0 0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 0 1

11              // TC 3, N = 11

0 0 1 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1

0 0 0 1 0 0 0 0 1 0 0

0 1 0 1 1 0 0 0 1 0 0

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0

#1 12            // Đầu ra của TC  thứ nhất

#2 10            // Đầu ra thứ 2 của  TC

#3 24            // Đầu ra của TC  thứ 3