Ma trận kì lạ


Submit solution

Points: 2 (partial)
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Cho một ma trận vuông cỡ \(N\)x\(N\), đề bài đảm bảo ma trận chỉ gồm toàn số 0 và duy nhất một số 1. Trong một bước, bạn có thể sử dụng 1 trong 2 thao tác sau:

  • Đảo vị trị hai cột liền kề nhau
  • Đảo vị trí hai hàng liền kề nhau

Bạn hãy tính số bước ít nhất để di chuyển số 1 vào chính giữa ma trận nếu có thể.

Input

Dòng đầu tiên gồm một số nguyên duy nhất là cỡ của ma trận \((1<=N<=10^3)\)

N dòng tiếp theo mỗi dòng gồm N số nguyên là các số của ma trận. Chúng chỉ có giá trị 0 hoặc 1

Output

Một số nguyên duy nhất là số bước ngắn nhất để di chuyển số 1 vào chính giữa ma trận. Trường hợp không thể di chuyển được thì in -1

Ví dụ

Input 1

3
0 0 1
0 0 0
0 0 0

Output 1

2

Input 2

2 
0 0
0 1

Output 2

-1

Giải thích

Ví dụ 1

  • Bước 1 : đảo vị trí hai cột 2 và 3
  • Bước 2 : đảo vị trí hai hàng 1 và 2

Ví dụ 2

  • Không có cách nào để đưa số 1 vào chính giữa ma trận

Comments

There are no comments at the moment.