Lines

      Комментарии к записи Lines отключены

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 1 неделя, 6 дн. назад.

  • Автор
    Сообщения
  • #3406

    Условие задачи взято с сайта acmp.ru:

    В таблице из N строк и N столбцов некоторые клетки заняты шариками, другие свободны. Выбран шарик, который нужно переместить, и место, куда его нужно переместить. Выбранный шарик за один шаг перемещается в соседнюю по горизонтали или вертикали свободную клетку. Требуется выяснить, возможно ли переместить шарик из начальной клетки в заданную, и, если возможно, то найти путь из наименьшего количества шагов.

    Входные данные
    В первой строке входного файла INPUT.TXT находится число N, в следующих N строках – по N символов. Символом точки обозначена свободная клетка, латинской заглавной O – шарик, @ – исходное положение шарика, который должен двигаться, латинской заглавной X – конечное положение шарика. (2 <= N <= 40)

    Выходные данные
    В выходной файл OUTPUT.TXT выведите в первой строке Yes, если движение возможно, или No, если нет. Если движение возможно, то далее следует вывести N строк по N символов – как и на вводе, но букву X, а также все точки по пути следует заменить плюсами. Если решений несколько, выведите любое.

    Примеры

    INPUT.TXT OUTPUT.TXT
    1 5
    ….X
    .OOOO
    …..
    OOOO.
    @….
    Yes
    +++++
    +OOOO
    +++++
    OOOO+
    @++++
    2 5
    ..X..
    …..
    OOOOO
    …..
    ..@..
    No

    Разбор решения задачи

    Для решения задачи можно использовать поиск в глубину. Для обхода двумерного лабиринта это означает что мы пробуем двигаться из начальной точки влево, вверх, вниз, вправо, при этом задан некоторый (любой) приоритет направлений движения. Это значит, что если движение влево имеет больший приоритет, чем вверх, но из текущей точки можно двигаться и влево, и вверх – то движение будет выполняться влево. Но если перемещение влево не даст результата, то мы попробуем пойти вверх (поиск с возвратами). Схематично работа такого алгоритма показана на рисунке:

    На рисунке показан пример лабиринта и возможный порядок его обхода. Такой порядок всегда можно изобразить в виде дерева, так как нет смысла возвращаться в точки, которые уже есть в нашем маршруте, т.е. путь является ацикличным.

    Описанный алгоритм можно изобразить в виде следующей блок-схемы:

    Реализация алгоритма на языке Си:

    #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;
    }

    В приведенной реализации структура point определяет координатную структуру точки. Во время работы алгоритма (функция kernel) в ячейки матрицы (matrix), хранящей лабиринт записывается длина пути из начальной точки до текущей. Если в ячейке, в которую возможен переход хранится значение, большее чем текущая длина пути (depth) – то в эту клетку записывается новая длина пути и поиск продолжится с этой клетки рекурсивно. Если же в клетке матрицы значение меньше depth[/cpp] - то ранее был найден более короткий путь в эту клетку, поэтому переходить в нее не надо. Функция [c]kernel пытается рекурсивно найти путь, переходя из текущей клетки во всех возможных направлениях.

Для ответа в этой теме необходимо авторизоваться.