Created
September 15, 2018 10:03
-
-
Save completejavascript/cc30327bd0efa12f75a4764a1ae0b26a to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
using namespace std; | |
const int MAX = 5; | |
const int MAX_QUEUE = 1000000; | |
const int MAX_INT = 1 << 30; | |
const int MAX_STATE = 50; | |
int N; //số lượng thùng | |
int Capacity[MAX]; //dung lượng mối thùng | |
int Water[MAX]; //lượng nước hiện tại mỗi thùng | |
int Need[MAX]; //lượng nước cần | |
int Answer; //kết quả | |
bool Flag, Finish; | |
// Đánh dấu trạng thái | |
int State[MAX_STATE][MAX_STATE][MAX_STATE][MAX_STATE]; | |
typedef struct Point | |
{ | |
int *water; | |
int step; | |
Point():step(0),water(0){} | |
Point(int st, int *wa):step(st),water(wa){} | |
}Point; | |
Point queue[MAX_QUEUE]; | |
int fr, re, leng; | |
/** | |
* copy mảng: từ mảng src sang mảng dst*/ | |
void CpyArray(int *dst, int *src) | |
{ | |
for(int i = 0; i < N; i++) | |
dst[i] = src[i]; | |
} | |
// implement hàng đợi vòng | |
void Enqueue(Point p) | |
{ | |
queue[re] = p; | |
re = (re + 1) % MAX_QUEUE; | |
leng++; | |
} | |
Point Dequeue() | |
{ | |
Point p = queue[fr]; | |
fr = (fr + 1) % MAX_QUEUE; | |
leng--; | |
return p; | |
} | |
/** | |
* Lấy giá trị của mảng 4 chiều tại một trạng thái | |
*/ | |
int GetValueState(int *tmp) | |
{ | |
int a,b,c,d; | |
a = b = c = d = 0; | |
if(N == 1) a = tmp[0]; | |
else if(N == 2) {a = tmp[0]; b = tmp[1];} | |
else if(N == 3) {a = tmp[0]; b = tmp[1]; c = tmp[2];} | |
else if(N == 4) {a = tmp[0]; b = tmp[1]; c = tmp[2]; d = tmp[3];} | |
return State[a][b][c][d]; | |
} | |
/** | |
* Xét giá trị value cho mảng 4 chiều tại trạng thái cho trước | |
*/ | |
void SetValueState(int *tmp, int value) | |
{ | |
int a,b,c,d; | |
a = b = c = d = 0; | |
if(N == 1) a = tmp[0]; | |
else if(N == 2) {a = tmp[0]; b = tmp[1];} | |
else if(N == 3) {a = tmp[0]; b = tmp[1]; c = tmp[2];} | |
else if(N == 4) {a = tmp[0]; b = tmp[1]; c = tmp[2]; d = tmp[3];} | |
State[a][b][c][d] = value; | |
} | |
// Implement BFS | |
void BFS(Point st) | |
{ | |
fr = re = leng = 0; | |
SetValueState(st.water,0); | |
Enqueue(st); | |
while(leng > 0) | |
{ | |
Point p = Dequeue(); | |
// Duyệt các thùng và thực hiện 3 hành động | |
for(int i = 0; i < N; i++) | |
{ | |
// Hành động 1: đổ hết nước đi | |
int old_water = p.water[i]; | |
p.water[i] = 0; | |
int *tmp1 = new int[N]; | |
CpyArray(tmp1, p.water); | |
// Kiểm tra xem trạng thái này đã có chưa | |
// nếu giá trị tại đó là MAX_INT nghĩa là chưa có | |
if(GetValueState(tmp1) == MAX_INT) | |
{ | |
SetValueState(tmp1, p.step + 1); | |
Enqueue(Point(p.step + 1, tmp1)); | |
} | |
p.water[i] = old_water; | |
// Hành động 2: Đổ đầy bằng 1 thùng khác | |
// Hành động này chỉ thực hiện khi thùng chưa đầy | |
if(p.water[i] < Capacity[i]) | |
{ | |
// thử đổ đầy bằng các thùng còn lại | |
for(int j = 0; j < N; j++) | |
{ | |
if(j == i) continue; | |
if(Capacity[i] - p.water[i] <= p.water[j]) | |
{ | |
int old_water1 = p.water[i], old_water2 = p.water[j]; | |
p.water[j] = p.water[j] - (Capacity[i] - p.water[i]); | |
p.water[i] = Capacity[i]; | |
int *tmp2 = new int[N]; | |
CpyArray(tmp2,p.water); | |
// Kiểm tra xem trạng thái này đã có chưa | |
// nếu giá trị tại đó là MAX_INT nghĩa là chưa có | |
if(GetValueState(tmp2) == MAX_INT) | |
{ | |
SetValueState(tmp2,p.step+1); | |
Enqueue(Point(p.step+1,tmp2)); | |
} | |
p.water[i] = old_water1; | |
p.water[j] = old_water2; | |
} | |
} | |
} | |
//Hành động 3: Đổ hết nước sang thùng khác nếu đủ chỗ | |
//Xét thử các thùng | |
for(int j = 0; j < N; j++) | |
{ | |
if(j == i) continue; | |
if(Capacity[j] - p.water[j] >= p.water[i]) | |
{ | |
int old_water1 = p.water[i], old_water2 = p.water[j]; | |
p.water[j] = p.water[j] + p.water[i]; | |
p.water[i] = 0; | |
int *tmp3 = new int[N]; | |
CpyArray(tmp3,p.water); | |
// Kiểm tra xem trạng thái này đã có chưa | |
// nếu giá trị tại đó là MAX_INT nghĩa là chưa có | |
if(GetValueState(tmp3) == MAX_INT) | |
{ | |
SetValueState(tmp3,p.step+1); | |
Enqueue(Point(p.step+1,tmp3)); | |
} | |
p.water[i] = old_water1; | |
p.water[j] = old_water2; | |
} | |
} | |
} | |
} | |
} | |
int main() | |
{ | |
ios::sync_with_stdio(false); | |
//freopen("input.txt","r",stdin); | |
int T; | |
cin >> T; | |
for(int tc = 0; tc < T; tc++) | |
{ | |
cin >> N; | |
for(int i = 0; i < N; i++) | |
{ | |
cin >> Capacity[i]; | |
Water[i] = Capacity[i]; | |
} | |
for(int i = 0; i < N; i++) | |
cin >> Need[i]; | |
Answer = MAX_INT; | |
for(int i = 0; i < MAX_STATE; i++) | |
for(int j = 0; j < MAX_STATE; j++) | |
for(int k = 0; k < MAX_STATE; k++) | |
for(int m = 0; m < MAX_STATE; m++) | |
State[i][j][k][m] = MAX_INT; | |
BFS(Point(0, Water)); | |
Answer = GetValueState(Need); | |
if(Answer == MAX_INT) cout << "NO" << endl; | |
else cout << Answer << endl; | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment