Beautiful Matrix

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho ma trận $5\times5$ chỉ gồm 24 số 0 và đúng một số 1. Mỗi thao tác được đổi chỗ hai hàng kề nhau hoặc hai cột kề nhau. Hãy tìm số thao tác ít nhất để đưa số 1 về ô chính giữa, tức hàng 3 cột 3 (đánh số từ 1).

Input

Năm dòng, mỗi dòng năm số nguyên 0 hoặc 1, cách nhau bởi dấu cách; có đúng một số 1.

Output

In số thao tác ít nhất.

Subtask

• Subtask 1 (20%): Khoảng cách Manhattan của số 1 tới tâm không quá 1; ma trận luôn 5x5 với đúng một số 1.

• Subtask 2 (30%): Khoảng cách Manhattan của số 1 tới tâm không quá 2; ma trận luôn 5x5 với đúng một số 1.

• Subtask 3 (50%): Khoảng cách Manhattan của số 1 tới tâm không quá 4; ma trận luôn 5x5 với đúng một số 1.

Ví dụ

Ví dụ 1

Input:

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

Output:

3

Giải thích:

Số 1 nằm ở (2,5). Cần |2-3|+|5-3|=3 lần đổi hàng/cột kề nhau.

Ví dụ 2

Input:

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

Output:

0

Giải thích:

Số 1 nằm ở (3,3). Cần |3-3|+|3-3|=0 lần đổi hàng/cột kề nhau.