-
Notifications
You must be signed in to change notification settings - Fork 48
/
Copy pathdonuocLAB.cpp
129 lines (123 loc) · 3.78 KB
/
donuocLAB.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include<vector>
#include<stdlib.h>
using namespace std;
/* Khai bao bien toan cuc */
const int MAX = 1000;
int maxp[3]; // Khai bao luong nuoc lon nhat moi binh co the nhan duoc {o day la 3 binh}
int p[3]; // Luong nuoc tai moi binh
/*Ham do nuoc tu binh p[x] sang p[y]*/
void donuoc(int ix, int iy) // Do nuoc tu binh p[ix] vao binh p[iy]
{
if(p[iy] == maxp[iy]) return; // Binh iy day thi khong do
if(p[ix] == 0) return; // Binh ix rong thi cung khong co gi de do
/*Sau moi lan do luon co 1 binh het hoac 1 binh tran*/
if(p[ix]+p[iy] > maxp[iy]) // Do tran binh iy
{
p[ix] = p[ix] + p[iy] - maxp[iy];
p[iy] = maxp[iy];
} else // Do het binh ix
{
p[iy] = p[iy] + p[ix];
p[ix] = 0;
}
// cout << p[1] << " " << p[2] << " " << p[3];
return;
}
/*Luu tru qua trinh di chuyen cua tung binh*/
struct LUUTRUQD
{
int move1;
int move2;
int move3;
};
struct LUUTRUQD print[MAX];
// print[x].move1 la luong nuoc tai binh 1 sau khi dich chuyen lan x
// print[x].move2 la luong nuoc tai binh 2 sau khi dich chuyen lan x
// print[x].move3 la luong nuoc tai binh 3 sau khi dich chuyen lan x
/*Danh dau vi tri da di qua*/
bool danhdau[MAX][MAX][MAX];
/*Printresult*/
void printresult(int c)
{
for (int i=0; i<c; i++)
{
cout << print[i].move1 << " " << print[i].move2 << " " << print[i].move3;
cout << endl;
}
cout << "-------" << endl;
return;
}
/*dfs*/
int run = 0;
void explore(int ix, int iy, int iz)
{
danhdau[p[ix]][p[iy]][p[iz]] = true;
print[run].move1 = p[ix]; /*Luu tru trang thai cua binh moi*/
print[run].move2 = p[iy]; /*khi do nuoc */
print[run].move3 = p[iz]; /*(Luu tru trang thai sau khi thuc hien donuoc)*/
if ((p[iy]==2) || (p[iz]==2)) // Neu gap trang thai can tim thi in ra man hinh
{
printresult(run+1);
}
run++;
donuoc(ix,iy); if ((!danhdau[p[ix]][p[iy]][p[iz]]) && ((p[iy]!=2) || (p[iz]!=2)))
{
explore(ix,iy,iz);
}
p[ix] = print[run-1].move1; // Chuyen nuoc ve trang thai truoc do
p[iy] = print[run-1].move2;
p[iz] = print[run-1].move3;
donuoc(ix,iz); if ((!danhdau[p[ix]][p[iy]][p[iz]]) && ((p[iy]!=2) || (p[iz]!=2)))
{
explore(ix,iy,iz);
}
p[ix] = print[run-1].move1;
p[iy] = print[run-1].move2;
p[iz] = print[run-1].move3;
donuoc(iy,ix); if ((!danhdau[p[ix]][p[iy]][p[iz]]) && ((p[iy]!=2) || (p[iz]!=2)))
{
explore(ix,iy,iz);
}
p[ix] = print[run-1].move1;
p[iy] = print[run-1].move2;
p[iz] = print[run-1].move3;
donuoc(iy,iz); if ((!danhdau[p[ix]][p[iy]][p[iz]]) && ((p[iy]!=2) || (p[iz]!=2)))
{
explore(ix,iy,iz);
}
p[ix] = print[run-1].move1;
p[iy] = print[run-1].move2;
p[iz] = print[run-1].move3;
donuoc(iz,ix); if ((!danhdau[p[ix]][p[iy]][p[iz]]) && ((p[iy]!=2) || (p[iz]!=2)))
{
explore(ix,iy,iz);
}
p[ix] = print[run-1].move1;
p[iy] = print[run-1].move2;
p[iz] = print[run-1].move3;
donuoc(iz,iy); if ((!danhdau[p[ix]][p[iy]][p[iz]]) && ((p[iy]!=2) || (p[iz]!=2)))
{
explore(ix,iy,iz);
}
p[ix] = print[run-1].move1;
p[iy] = print[run-1].move2;
p[iz] = print[run-1].move3;
return;
}
int main()
{
cout << "Nhap gia tri luong nuoc toi da trong cac binh" << endl;
cout << "(Binh 2 va binh 3 luon day)" << endl;
cout << "Nhap : ";
cin >> maxp[1] >> maxp[2] >> maxp[3];
// maxp[1] = 10; maxp[2] = 7; maxp[3] = 4;
p[2] = maxp[2]; // Ban dau binh 2 day
p[3] = maxp[3]; // Ban dau binh 3 day
for (int i=0; i<MAX; i++)
for (int j=0; j<MAX; j++)
for (int k=0; k<MAX; k++)
danhdau[i][j][k] = false;
explore(1,2,3);
return 0;
}