Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstring>
- #include <iostream>
- using namespace std;
- struct rightWay {
- int A[3][3];
- rightWay *next;
- rightWay *prev;
- };
- struct allWays {
- int A[3][3];
- allWays *next;
- };
- const int position[4][2] = {
- {-1, 0},
- {0, 1},
- {1, 0},
- {0, -1}
- };
- int findZeroPosition(int startPosition[3][3], int *zeroX, int *zeroY) {
- for (int i = 0; i < 3; i++)
- for (int j = 0; j < 3; j++)
- if (startPosition[i][j] == 0) {
- *zeroX = i;
- *zeroY = j;
- return 0;
- }
- return -1;
- }
- bool compareArrays(int A[3][3], int B[3][3]) {
- for (int i = 0; i < 3; i++)
- for (int j = 0; j < 3; j++)
- if (A[i][j] != B[i][j])
- return false;
- return true;
- }
- bool compareArrays(int **swapResult, allWays *headAllWays) {
- while (headAllWays != nullptr) {
- int flag = 0;
- for (int i = 0; i < 3; i++)
- for (int j = 0; j < 3; j++) {
- if (headAllWays->A[i][j] == swapResult[i][j])
- flag++;
- }
- if (flag == 9)
- return true;
- headAllWays = headAllWays->next;
- }
- return false;
- }
- int **swap(int currentArray[3][3], int zeroX, int zeroY, int move) {
- int **array = new int *[3];
- for (int i = 0; i < 3; i++) {
- array[i] = new int[3];
- }
- memcpy(array, currentArray, 9 * sizeof(int));
- array[zeroX][zeroY] = currentArray[zeroX + position[move][0]][zeroY + position[move][1]];
- array[zeroX + position[move][0]][zeroY + position[move][1]] = 0;
- return array;
- }
- int main() {
- rightWay *headRightWay, *currentRightWay = new rightWay;
- allWays *headAllWays, *currentAllWays = new allWays;
- int startPosition[3][3] = {
- {5, 8, 3},
- {4, 0, 2},
- {7, 6, 1}
- };
- memcpy(currentRightWay->A, startPosition, 9 * sizeof(int));
- headRightWay = currentRightWay;
- memcpy(currentAllWays->A, startPosition, 9 * sizeof(int));
- headAllWays = currentAllWays;
- int endPosition[3][3] = {
- {1, 2, 3},
- {4, 5, 6},
- {7, 8, 0}
- };
- int zeroX, zeroY;
- findZeroPosition(startPosition, &zeroX, &zeroY);
- do {
- for (int i = 0; i < 4; i++) {
- if ((zeroX + position[i][0] >= 0) && (zeroX + position[i][0] <= 2) && (zeroY + position[i][1] >= 0) &&
- (zeroY + position[i][1] <= 2)) {
- int **swapResult = swap(currentAllWays->A, zeroX, zeroY, i);
- if (!compareArrays(swapResult, headAllWays)) {
- cout << "ok!";
- return 0;
- }
- }
- }
- } while (!compareArrays(currentRightWay->A, endPosition));
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement