Created
September 15, 2018 05:48
-
-
Save completejavascript/1f5ec78c593f761ac2371e858c66f105 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_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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment