Bài toán lật đồng xu
Mọi người làm chơi nhé
Có 16 đồng xu xếp thành bảng 4x4, mỗi đồng xu có thể úp hoặc ngửa như hình vẽ bên.
Tại mỗi bước ta có phép biến đổi sau: Chọn một đồng xu và thay đổi trạng thái của đồng xu đó và tất cả các đồng xu nằm ở các ô chung cạnh (úp thành ngửa, ngửa thành úp).
Yêu cầu: Cho trước một trạng thái các đồng xu, hãy lập trình tìm số phép biến đổi ít nhất để đưa về trạng thái tất cả các đồng xu hoặc đều úp hoặc đều ngửa.
Input
Gồm 4 dòng, mỗi dòng gồm 4 kí tự miêu tả trạng thái của mỗi đồng xu. Kí tự ‘w’ (white) thể hiện đồng xu đang ngửa, kí tự ‘b’ (black) thể hiện đồng xu úp.
Output
In ra số phép biến đổi ít nhất để đưa 16 đồng xu về tất cả trạng thái đều úp hoặc đều ngửa. Nếu không thể thực hiện được, in ra ”Impossible”.
Example
Test 1:
Input:
wbwb
bwbw
wbwb
bwbw
Output:
Impossible
Test 2:
Input:
bwbb
wwwb
bwbb
bbbb
Output:
1
Nguồn: http://www.spoj.com/PTIT/problems/P146PROA/
