Link Sub: http://www.spoj.com/PTIT/problems/P146PROA/
Người Gửi: Dương Lee
- Problem:
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.
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:
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”.
Input
wbwb
bwbw
wbwb
bwbw
Output:
Impossible
Input
bwbb
wwwb
bwbb
bbbb
Output:
1
- Solution:
- Bài này sinh nhị phân chọn lật đồng xu (Ở đây mình sinh nhị phân trên mảng 1 chiều rồi chuyển sang 2 chiều).
- Code dưới đây nếu giá trị là 1 thì chọn lật đồng xu đó (đồng thời cũng lật các đồng xu xung quanh nó), nếu giá trị là 0 thì giữ nguyên.
- Sau đó kiểm tra lại xem nó có cùng úp hoặc ngửa hay không? nều cùng thì số lượng giá trị 1 là số lần đổi và ta chỉ cần lấy min là được.Input
bwbb
wwwb
bwbb
bbbb
Output:
1
- Code:
C++:
https://ideone.com/UWP7Hb
#include <iostream>
#include <math.h>
using namespace std;
char info[5][5];
void read ()
{
for (int i=1; i<=4; i++)
{
for (int j=1; j<=4; j++)
cin>>info[i][j];
}
}
int arr[25];
int coins[5][5];
int _1Dto2D ()
{
int k=1;
int count = 0;
for (int i=1; i<=4; i++)
{
for (int j=1; j<=4; j++)
{
coins[i][j]=arr[k];
if (arr[k]==1) count++;
k++;
}
}
return count;
}
char rs[5][5];
int x_xq[]={+1, +0, -1, +0};
int y_xq[]={+0, -1, +0, +1};
void latxu ()
{
//Cop:
for (int i=1; i<=4; i++)
{
for (int j=1; j<=4; j++)
rs[i][j]=info[i][j];
}
for (int i=1; i<=4; i++)
{
for (int j=1; j<=4; j++)
{
if (coins[i][j]==1)
{
if (rs[i][j]=='b') rs[i][j]='w';
else rs[i][j]='b';
for (int k=0; k<4; k++)
{
int X=j+x_xq[k];
int Y=i+y_xq[k];
if (X>=1 && X<=4 && Y>=1 && Y<=4)
{
if (rs[Y][X]=='b') rs[Y][X]='w';
else rs[Y][X]='b';
}
}
}
}
}
}
int check ()
{
char init = rs[1][1];
for (int i=1; i<=4; i++)
{
for (int j=1; j<=4; j++)
{
if (rs[i][j]!=init) return 0;
}
}
return 1;
}
char tt[5][5];
int t2[5][5];
int Ans = 25;
void sinhNP (int u)
{
if (u>16)
{
int x = _1Dto2D ();
latxu ();
if (check()==1) Ans = min (Ans, x);
}
else
{
arr[u]=0;
sinhNP (u+1);
arr[u]=1;
sinhNP (u+1);
}
}
int main ()
{
read ();
sinhNP (1);
if (Ans != 25) cout<<Ans;
else cout<<"Impossible";
return 0;
}