Валентин Витринский
S:22:17:49 03.06
R:22:17:50 03.06
3. Var_str.c
#include <stdlib.h>
#include *Var_str.h*
Node *createNode(int x, int y, int xDir, int yDir) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->x = x;
newNode->y = y;
newNode->xDir = xDir;
newNode->yDir = yDir;
newNode->next = NULL;
return newNode;
}
void pushNode(Node **stack, Node *newNode) {
newNode->next = *stack;
*stack = newNode;
}
Node *popNode(Node **stack) {
if (*stack == NULL) {
return NULL;
}
Node *temp = *stack;
*stack = (*stack)->next;
return temp;
}
int isStackEmpty(Node *stack) {
return stack == NULL;
}
4. Alg.c
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include *Var_str.h*
#define MAX_MAP_SIZE 100
typedef struct {
int x, y;
int distance;
int xDir, yDir;
} Node;
int main() {
// Загрузка данных из файла
FILE *file = fopen(*map.txt*, *r*);
if (file == NULL) {
printf(*Ошибка: не удалось открыть файл map.txt\n*);
return 1;
}
int mapSize, numObstacles;
fscanf(file, *%d %d*, &mapSize, &numObstacles);
int obstacles[MAX_MAP_SIZE][MAX_MAP_SIZE] = {0};
for (int i = 0; i < numObstacles; i++) {
int x1, y1, x2, y2;
fscanf(file, *%d %d %d %d*, &x1, &y1, &x2, &y2);
for (int x = x1; x <= x2; x++) {
for (int y = y1; y <= y2; y++) {
obstacles[x][y] = 1;
}
}
}
fclose(file);
// Начальная и конечная точки
int startX, startY, endX, endY;
printf(*Введите начальную точку (x y): *);
scanf(*%d %d*, &startX, &startY);
printf(*Введите конечную точку (x y): *);
scanf(*%d %d*, &endX, &endY);
// Алгоритм A*
Node [club31728388|*openList] = NULL;
Node [club128419849|*closedList] = NULL;
Node *currentNode = createNode(startX, startY, 0, 0);
pushNode(&openList, currentNode);
while (!isStackEmpty(openList)) {
currentNode = popNode(&openList);
pushNode(&closedList, currentNode);
if (currentNode->x == endX && currentNode->y == endY) {
// Путь найден, восстановление маршрута
printf(*Путь найден:\n*);
while (currentNode != NULL) {
printf(*(%d, %d)\n*, currentNode->x, currentNode->y);
currentNode = createNode(currentNode->x - currentNode->xDir, currentNode->y - currentNode->yDir, -currentNode->xDir, -currentNode->yDir);
pushNode(&openList, currentNode);
currentNode = popNode(&closedList);
}
return 0;
}
// Поиск соседних узлов
for (int dx = -1; dx <= 1; dx++) {
for (int dy = -1; dy <= 1; dy++) {
if (dx == 0 && dy == 0) {
continue;
}
int newX = currentNode->x + dx;
int newY = currentNode->y + dy;
if (newX >= 0 && newX < mapSize && newY >= 0 && newY < mapSize && !obstacles[newX][newY]) {
Node *neighborNode = createNode(newX, newY, dx, dy);
pushNode(&openList, neighborNode);
}
}
}
}
printf(*Путь не найден.\n*);
return 0;
}