#include using namespace std; #define numVl 3 struct thNde { thNde* parent; int mat[numVl][numVl]; int x, y; int cost; int level; }; int thPrntMtrx(int mat[numVl][numVl]) { for (int q = 0; q < numVl; q++) { for (int j = 0; j < numVl; j++) printf("%d ", mat[q][j]); printf("\n"); } } thNde* newNode(int mat[numVl][numVl], int x, int y, int newX, int newY, int level, thNde* parent) { thNde* node = new thNde; node->parent = parent; memcpy(node->mat, mat, sizeof node->mat); swap(node->mat[x][y], node->mat[newX][newY]); node->cost = INT_MAX; node->level = level; node->x = newX; node->y = newY; return node; } int row[] = { 1, 0, -1, 0 }; int col[] = { 0, -1, 0, 1 }; int calculateCost(int starting[numVl][numVl], int resltng[numVl][numVl]) { int count = 0; for (int q = 0; q < numVl; q++) for (int j = 0; j < numVl; j++) if (starting[q][j] && starting[q][j] != resltng[q][j]) count++; return count; } int isSafe(int x, int y) { return (x >= 0 && x < numVl && y >= 0 && y < numVl); } void printPath(thNde* root) { if (root == NULL) return; printPath(root->parent); thPrntMtrx(root->mat); printf("\n"); } struct comp { bool operator()(const thNde* lhs, const thNde* rhs) const { return (lhs->cost + lhs->level) > (rhs->cost + rhs->level); } }; void slve(int starting[numVl][numVl], int x, int y, int resltng[numVl][numVl]) { priority_queue, comp> pq; thNde* root = newNode(starting, x, y, x, y, 0, NULL); root->cost = calculateCost(starting, resltng); pq.push(root); while (!pq.empty()) { thNde* min = pq.top(); pq.pop(); if (min->cost == 0) { printPath(min); return; } for (int q = 0; q < 4; q++) { if (isSafe(min->x + row[q], min->y + col[q])) { thNde* child = newNode(min->mat, min->x, min->y, min->x + row[q], min->y + col[q], min->level + 1, min); child->cost = calculateCost(child->mat, resltng); pq.push(child); } } } } int main() { int starting[numVl][numVl] = { {1, 2, 3}, {5, 6, 0}, {7, 8, 4} }; int resltng[numVl][numVl] = { {1, 2, 3}, {5, 8, 6}, {0, 7, 4} }; int x = 1, y = 2; slve(starting, x, y, resltng); return 0; } I need someone explain this code to me please !
#include <bits/stdc++.h>
using namespace std;
#define numVl 3
struct thNde {
thNde* parent;
int mat[numVl][numVl];
int x, y;
int cost;
int level;
};
int thPrntMtrx(int mat[numVl][numVl]) {
for (int q = 0; q < numVl; q++)
{
for (int j = 0; j < numVl; j++)
printf("%d ", mat[q][j]);
printf("\n");
}
}
thNde* newNode(int mat[numVl][numVl], int x, int y, int newX,
int newY, int level, thNde* parent) {
thNde* node = new thNde;
node->parent = parent;
memcpy(node->mat, mat, sizeof node->mat);
swap(node->mat[x][y], node->mat[newX][newY]);
node->cost = INT_MAX;
node->level = level;
node->x = newX;
node->y = newY;
return node;
}
int row[] = { 1, 0, -1, 0 };
int col[] = { 0, -1, 0, 1 };
int calculateCost(int starting[numVl][numVl], int resltng[numVl][numVl]) {
int count = 0;
for (int q = 0; q < numVl; q++)
for (int j = 0; j < numVl; j++)
if (starting[q][j] && starting[q][j] != resltng[q][j])
count++;
return count;
}
int isSafe(int x, int y) {
return (x >= 0 && x < numVl && y >= 0 && y < numVl);
}
void printPath(thNde* root) {
if (root == NULL)
return;
printPath(root->parent);
thPrntMtrx(root->mat);
printf("\n");
}
struct comp {
bool operator()(const thNde* lhs, const thNde* rhs) const
{
return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);
}
};
void slve(int starting[numVl][numVl], int x, int y,
int resltng[numVl][numVl]) {
priority_queue<thNde*, std::vector<thNde*>, comp> pq;
thNde* root = newNode(starting, x, y, x, y, 0, NULL);
root->cost = calculateCost(starting, resltng);
pq.push(root);
while (!pq.empty()) {
thNde* min = pq.top();
pq.pop();
if (min->cost == 0) {
printPath(min);
return;
}
for (int q = 0; q < 4; q++) {
if (isSafe(min->x + row[q], min->y + col[q])) {
thNde* child = newNode(min->mat, min->x,
min->y, min->x + row[q],
min->y + col[q],
min->level + 1, min);
child->cost = calculateCost(child->mat, resltng);
pq.push(child);
}
}
}
}
int main() {
int starting[numVl][numVl] =
{
{1, 2, 3},
{5, 6, 0},
{7, 8, 4}
};
int resltng[numVl][numVl] =
{
{1, 2, 3},
{5, 8, 6},
{0, 7, 4}
};
int x = 1, y = 2;
slve(starting, x, y, resltng);
return 0;
}
I need someone explain this code to me please !
Step by step
Solved in 3 steps with 1 images
How can I replace this
#include <bits/stdc++.h>
And I want to use class instead of struct
by Bartleby Expert
