Câu đố của Simon

Submit solution
Points: 3.4 (partial)
Time limit: 1.0s
JAVA11 2.0s
Pypy 3 2.0s
Memory limit: 98M
JAVA11 977M
Pypy 3 977M
Author:
creator
Problem type

Có \(16\) đồng xu xếp thành bảng \(4 \times 4\), mỗi đồng xu có thể úp hoặc ngửa. Tại mỗi bước ta thể chọn một đồng xu rồi thay đổi trạng thái của đồng xu đó và tất cả các đồng xu chung cạnh (úp thành ngửa, ngửa thành úp).

Cho hai trạng thái các đồng xu, hãy tìm xem để biến đổi từ trạng thái này sang trạng thái kia cần tối thiểu bao nhiêu bước.

Đầu vào

Dòng đầu tiên chứa số nguyên \(t\), số test con \((1 \le t \le 100000)\).

Các dòng tiếp theo, mỗi \(8\) dòng đặc tả một test con:

  • \(4\) dòng đầu tiên, mỗi dòng chứa \(4\) kí tự (\(0\) hoặc \(1\)) viết liền mô tả trạng thái bắt đầu.
  • \(4\) dòng tiếp theo, mỗi dòng chứa \(4\) kí tự (\(0\) hoặc \(1\)) viết liền mô tả trạng thái kết thúc.

Mỗi test con được ngăn cách bởi một dấu cách.

Đầu ra

\(t\) dòng, mỗi dòng chứa duy nhất một số nguyên, nếu không có cách biến đổi nào thì xuất ra \(-1\).

Subtask

\(40\%\) số test có \(t = 1\).

Ví dụ

Đầu vào:

2
0000
0100
1110
0100
0000
0010
0111
0010

1100
0000
1100
0000
0000
0000
0000
0000

Đầu ra:

2
-1
QDUY

Comments