SPOJ.COM – Thuật toán bài CHESSCBG - Bàn cờ thế
Đề bài:
Một bàn cờ thế là một bảng gồm 4 dòng, 4 cột. Mỗi thế cờ là một cách sắp xếp 8 quân cờ, hai quân khác nhau ở hai ô khác nhau. Bài toán đặt ra là cho hai thế cờ 1 và 2, hãy tìm một số ít nhất bước di chuyển quân để chuyển từ thế 1 sang thế 2; một bước di chuyển quân là một lần chuyển quân cờ sang ô trống kề cạnh với ô quân cờ đang đứng.
Đầu vào:
Từ file văn bản gồm 8 dòng, mỗi dòng là một xâu nhị phân độ dài 4 mà số 1/0 tương ứng với vị trí có hoặc không có quân cờ. Bốn dòng đầu là thế cờ 1, bốn dòng sau là thế cờ 2.
Đầu ra:
Gồm 1 dòng duy nhất là số bước chuyển quân ít nhất.
Ví dụ:
Đầu vào:
1111
0000
1110
0010
1010
0101
1010
0101
Đầu ra:
4
Các bạn có thể tham khảo link gốc đề bài và submit code tại đây: http://vn.spoj.com/problems/CHESSCBG/
Phân tích:
-
Ở đây, ma trận đầu vào tôi sẽ lưu nó dưới dạng mảng 1 chiều. Công thức để quy đổi từ tọa độ 1 điểm trên ma trận thành tọa độ 1 điểm trên mảng và ngược lại như sau:
- Từ điểm có tọa độ
[r][c]trên ma trận thì tọa độ trên mảng là: r*N + c (trong đó N là số cột của ma trận. Ở đây N = 4). Ví dụ: một điểm ở tọa độ[1][2](hàng 1, cột 2) thì ở trên mảng nó sẽ tương ứng với điểm 1*4 + 2 = 6 (chỉ số tính từ 0) - Ngược lại, từ một điểm ở trên mảng có tọa độ là t thì ở trên mảng, tọa độ của nó là: c = t % N và r = (t - c)/4. Lấy luôn ví dụ trên, với điểm trên mảng có tọa độ t = 6, thì trên mảng nó sẽ có tọa độ: c = 6 % 4 = 2 và r = (6 - 2) /4 = 1.
- Từ điểm có tọa độ
-
Như vậy, thế cờ 1 và thế cờ 2 đều có thể biểu diễn được dưới dạng mảng 1 chiều gồm 16 phần tử. Ở đây, tôi sẽ sử dụng thuật toán tìm kiếm theo chiều rộng - BFS với trạng thái đầu là thế cờ 1 và trạng thái đích là thế cờ 2. Để thực hiện điều này, tôi cần phải có một mảng để lưu số bước ít nhất mà từ thế cờ 1 tới thế cờ đó.
-
Ở đây có một điều đặc biệt đó là các phần tử của mảng chỉ bao gồm các số 0 và 1. Do đó, tôi hoàn toàn có thể coi nó như là một số nhị phân. Vì vậy, tôi sẽ chuyển nó thành số thập phân tương ứng để biểu diễn trạng thái đó. Với ví dụ đầu bài, thế cờ 1 là:
1111 0000 1110 0010
Tôi chuyển nó thành mảng: 1111.0000.1110.0010. Dãy số này tương ứng với số: 61666. Đến đây là bài toán đã trở nên đơn giản hơn rồi phải không các bạn.
Lời giải:
(Các bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của tôi nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code tôi viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của các bạn.)
Code C/C++:
| #include<iostream> | |
| using namespace std; | |
| const int MAX_INT = 1 << 30; | |
| const int MAX = 100000; | |
| // Mảng lưu giá trị lũy thừa của 2 tại các vị trí. | |
| // Ví dụ tại vị trí 0 - tương ứng với 2^15 = 32768 | |
| const int Po2[16] = {32768, 16384, 8192, 4096, 2048, 1024, | |
| 512, 256, 128, 64, 32, 16, 8, 4, 2, 1}; | |
| int MinStep; // Số bước nhỏ nhất để chuyển từ Map nguồn thành Map đích. | |
| int Init[2]; // Lưu trạng thái của Map đầu và cuối dưới dạng số. | |
| int Mark[MAX]; // Đánh dấu với mỗi trạng thái thì số bước nhỏ nhất là bao nhiêu | |
| int State[16]; // Trạng thái của ma trận. | |
| // Biểu diễn hàng đợi vòng | |
| int queue[MAX]; | |
| int fr, re, leng; | |
| void Enqueue(int stt) | |
| { | |
| queue[re] = stt; | |
| re = (re + 1) % MAX; | |
| leng++; | |
| } | |
| int Dequeue() | |
| { | |
| int stt = queue[fr]; | |
| fr = (fr + 1) % MAX; | |
| leng--; | |
| return stt; | |
| } | |
| /* | |
| * @PARAM: value : số đầu vào cần chuyển đổi thành ma trận trạng thái | |
| */ | |
| void ConvertInt2Matrix(int value) | |
| { | |
| for(int i = 0; i < 16; i++) | |
| { | |
| int _c = i % 4; | |
| int _r = (i - _c) / 4; | |
| // Kiểm tra xem chữ số nào mà bằng 1 thì cho giá trị ma trận = 1 | |
| // ngược lại là 0 | |
| if((1 << i) & value) State[15 - i] = 1; | |
| else State[15 - i] = 0; | |
| } | |
| } | |
| int drow[4] = {-1,0,1, 0}; | |
| int dcol[4] = { 0,1,0,-1}; | |
| void BFS(int init) | |
| { | |
| fr = re = leng = 0; | |
| for(int i = 0; i < MAX; i++) | |
| Mark[i] = MAX_INT; | |
| // Trạng thái đầu tiên | |
| Mark[init] = 0; | |
| Enqueue(init); | |
| while(leng > 0) | |
| { | |
| int begin = Dequeue(); | |
| // Chuyển giá trị state vào ma trận. | |
| ConvertInt2Matrix(begin); | |
| // Duyệt các trạng thái. | |
| for(int i = 0; i < 16; i++) | |
| if(State[i] == 1) | |
| { | |
| // Tính tọa độ tương ứng trên ma trận | |
| int _c = i % 4; | |
| int _r = (i - _c) / 4; | |
| // Kiểm tra 4 hướng xem với số 1 di chuyển 4 hướng | |
| // thì trạng thái tiếp theo là gì. | |
| for(int j = 0; j < 4; j++) | |
| { | |
| int r = _r + drow[j]; | |
| int c = _c + dcol[j]; | |
| if(r >= 0 && r < 4 && c >= 0 && c < 4 && State[r*4+c] == 0) | |
| { | |
| // Tính giá trị của số mới | |
| // với việc số 1 ở vị trí ban đầu (_r*4 + _c) chuyển thành 0 | |
| // số 0 ở vị trí (r*4 + c) chuyển thành 1 | |
| int value = begin + Po2[r*4+c] - Po2[_r*4+_c]; | |
| if((Mark[value] == MAX_INT || Mark[value] > Mark[begin] + 1)) | |
| { | |
| Mark[value] = Mark[begin] + 1; | |
| Enqueue(value); | |
| } | |
| } | |
| } | |
| } | |
| } | |
| } | |
| int main() | |
| { | |
| ios::sync_with_stdio(false); | |
| //freopen("input.txt","r",stdin); | |
| // Nhập đầu vào. | |
| // Convert trạng thái Map thành số nguyên, | |
| // vì tại mỗi ô của Map chỉ có 2 trạng thái 0, 1. | |
| for(int k = 0; k < 2; k++) | |
| { | |
| Init[k] = 0; | |
| for(int i = 0; i < 4; i++) | |
| { | |
| char temp[5]; | |
| cin >> temp; | |
| for(int j = 0; j < 4; j++) | |
| Init[k] = Init[k] * 2 + (temp[j] - '0'); | |
| } | |
| } | |
| // BFS từ trạng thái ban đầu cho đến khi gặp trạng thái đích | |
| BFS(Init[0]); | |
| // In kết quả | |
| cout << Mark[Init[1]] << endl; | |
| return 0; | |
| } |
Code by Phạm Văn Lâm.