Решения задач acmp.ru Вторник, 29.09.2020, 00:01 Приветствую Вас Гость | RSS
 Меню сайта

Категории раздела
 Pascal [121] C++ [76]

 Поиск

Мини-чат
 --15 сек30 сек1 мин2 мин
 200

 Легкий заработок!

 Статистика Онлайн всего: 1 Гостей: 1 Пользователей: 0

 Форма входа

 Главная » Файлы » C++

0381 Lines

### Скачать файл можно после просмотра рекламы:

05.06.2012, 03:10
#include <stdio.h>
#include <memory.h>

#define BUFFER_SIZE n*n+2

struct point
{
unsigned int x, y;
};

unsigned int n = 0;
unsigned int **matrix = NULL;

point target = {0, 0};

point * way_buffer = NULL;
point * buffer = NULL;
unsigned int length;

void kernel(unsigned int depth, unsigned int x, unsigned int y)
{
if (x == target.x && y == target.y && depth < length)
{
length = depth;
memcpy(way_buffer, buffer, sizeof(point) * depth);
}
else
{
if (x > 0) if (matrix [x-1][y] > depth)
{
buffer [depth].x = x-1;
buffer [depth].y = y;
matrix [x-1][y] = depth;
kernel(depth + 1, x-1, y);
}
if (y > 0) if (matrix [x][y-1] > depth)
{
buffer [depth].x = x;
buffer [depth].y = y-1;
matrix [x][y-1] = depth;
kernel(depth + 1, x, y-1);
}
if (x < n-1) if (matrix [x+1][y] > depth)
{
buffer [depth].x = x+1;
buffer [depth].y = y;
matrix [x+1][y] = depth;
kernel(depth + 1, x+1, y);
}
if (y < n-1) if (matrix [x][y+1] > depth)
{
buffer [depth].x = x;
buffer [depth].y = y+1;
matrix [x][y+1] = depth;
kernel(depth + 1, x, y+1);
}
}
}

int main()
{
point start = {0, 0};

FILE *f = fopen("input.txt", "r");
fscanf(f, "%d", &n);

char ** chr_matrix = new char* [n];
char *tmp = new char [n+2];
matrix = new unsigned int* [n];
for (int  i = 0; i<n; i++)
{
matrix [i] = new unsigned int [n];
chr_matrix [i] = new char [n+1];
memset(matrix [i], 255, sizeof(unsigned int) * n);
memset(chr_matrix [i], '.', sizeof(char) * n);

fscanf(f, "%s", tmp);
for (int j = 0; j<n; j++)
{
switch (tmp[j])
{
case 'O':
matrix [i][j] = 0;
chr_matrix [i][j] = 'O';
break;

case 'X':
target.x = i;
target.y = j;
break;

case '@':
start.x = i;
start.y = j;
matrix [i][j] = 0;
chr_matrix [i][j] = '@';
break;
}
}
chr_matrix [i][n] = 0;
}
fclose(f);

length = BUFFER_SIZE;
buffer = new point [BUFFER_SIZE];
way_buffer = new point [BUFFER_SIZE];
memset(buffer, NULL, sizeof(point) * BUFFER_SIZE);
memset(way_buffer, NULL, sizeof(point) * BUFFER_SIZE);

kernel(0, start.x, start.y);

if (length == BUFFER_SIZE)
{
f = fopen("output.txt", "wt");
fprintf(f, "No");
fclose(f);
}
else
{
for (int i = 0; i<length; i++)
chr_matrix [way_buffer[i].x][way_buffer[i].y] = '+';

f = fopen("output.txt", "wt");
fprintf(f, "Yes\n");
for (int i = 0; i<n; i++)
{
fprintf(f, "%s\n", chr_matrix[i]);
}
fclose(f);
}

return 0;
}
Категория: C++ | Добавил: shum
Просмотров: 1378 | Загрузок: 0
 Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
 Это интересно!