Общение

russian-robots@conference.jabber.ru - Чат, в котором можно поболтать об электронике, создании роботов и программировании.
Как мне зайти в чат?

 Обсуждение

Не стесняйтесь оставлять комментарии, мне интересно и важно ваше мнение!
  • Wadimka: Подскажу где взять недорого строчники, идете/едите в любую контору которая ...
  • Vladimir: Об этом датчике я тоже знаю, хотелось с чегото начать изучать МК, а не слеп ...
  • Vladimir: Спсиба
  • Евгений: Стоит поставить инфракрасный датчик движения и не городить ничего :) Литера ...
  • Vladimir: Добрый день Евгений. Это мне для дома в кладовку. При входе на двери стоит ...
  • Евгений: Фотобарьер? По подробнее расскажите.
  • Vladimir: Добрый день. Прошу вас помочь в реализации пректа фотобарер на Tiny45, со с ...
  • Евгений: С таким кодом даже http://caxapa.ru/codebook/?search=BLSH ничего не находит ...
  • Поиск кратчайшего пути к выходу из лабиринта на C++

    10th Ноябрь 2011 | Метки: ,

    Расскажу как я искал выход из лабиринта в своей курсовой.

    Задание

    Лабиринт можно разбить на клетки, поэтому лабиринт задан в виде матрицы, в которой ячейка со значением 1 – стена, 0 – проход, 2 – человек, которому нужно выйти из лабиринта по кратчайшему пути. Распечатать / выделить пройденный путь. Выход из лабиринта один и человек тоже один.

    Алгоритм поиска кратчайшего пути к выходу из лабиринта

    Сначала матрица лабиринта загружается из текстового файла в динамический двумерный массив. Далее ищем координаты выхода из лабиринта, перебирая «по периметру» матрицы все элементы, пока не найдём элемент, равный нулю. Если такого элемента нет – значит выхода из лабиринта нет. Если есть, присваиваем его координаты переменной exit типа Point.

    1. Поиск кратчайшего пути к выходу из лабиринта начинается с присваивания переменной temp типа int значения 2 (клетка с человеком).

    2. Далее перебираем все элементы лабиринта, пока не найдем элемент со значением, равным temp.

    3. Как найдем – анализируем соседние к нему элементы при помощи функции check(x, y). Если какой-нибудь из этих элементов равен нулю (свободный проход), то присваиваем ему значение temp+1. Если такой элемент существует, то функция check(x, y) вернет 1, иначе 0.

    4. Тем самым, просуммировав возвращаемые значения функции check(x, y) мы можем узнать, изменилась ли хотя бы одна клетка из лабиринта за проход или нет. Если нет – то значит человек замурован и можно завершить выполнение программы. Иначе – продолжить выполнение.

    5. Если элемент матрицы с координатами выхода из лабиринта равен нулю, то плюсуем temp и повторяем цикл сначала (переходим ко 2-ому пункту).

    Если клетка выход из лабиринта не ноль, то присваиваем переменной значение этой самой клетки.

    steps = maze[exit.y][exit.x];

    Количество совершенных ходов равняется steps – 2.

    Алгоритм поиска пройденного пути

    По условию задачи надо распечатать или как-нибудь выделить пройденный путь.

    Пройденный путь ищется следующим образом:

    1. Начиная от выхода из лабиринта анализируем соседние элементы, на предмет равенства их значения со значением steps – 1, steps – 2, steps – 3 и т.д. Если равенство выполняется, то присваиваем этому элементу значение 0. И так пока не дойдём до элемента со значением 2 (отсюда человек начал идти к выходу).

    Исходный код

    #include <iostream.h>
    #include <stdio.h>
    #include <io.h>
     
    #define MEN 2
    #define LF 10
    #define SPACE 32
    #define ORIGINAL_MAZE 0
    #define MAZE_WITH_PATH 1
     
    struct Point
    {
    	int x;
    	int y;
    } exit;
     
    int** maze;
    int sizex = 0, sizey = 0;
    int load_maze()
    {
    	int i, j, filesize = 0, x = 0, y = 0;
    	char* cc;
    	FILE *F;
    	//Пытаемся открыть текстовой файл для чтения:
    	F = fopen("maze.txt","rt");
    	if( F==NULL )
    		return 0;
    	//Создаем массив, в который поместим байты из файлы:
    	filesize = filelength(fileno(F));
    	cc = new char[filesize];
    	//Загружаем в массив байты из файла:
    	for(i=0;i!=filesize;i++)
    		cc[i] = getc(F);
    	fclose(F);
    	//Рассчитываем размеры матрицы лабиринта:
    	i = 0;
    	while(cc[i] != LF)
    	{
    		if(cc[i] != SPACE)
    			sizex++;
    		i++;
    	}
    	sizey = filesize/(sizex*2);
    	//Теперь размер лабиринта известен, инициализируем матрицу:
    	maze = new int*[sizey];
    	while(y != sizey)
    		maze[y++] = new int[sizex];
    	//Заполняем матрицу лабиринта данными из файла
    	i=0;
    	for(y = 0;y!=sizey;y++)
    	{
    		for(j=0;j!=sizex;j++)
    		{
    			maze[y][x] = cc[i]-48;
    			x++;
    			i+=2;
    		}
    		x=0;
    	}
    	return 1;
    }
     
    int temp = MEN;
    int check(int x, int y)
    {
    	int cnt = 0;
    	if(x != 0 && maze[y][x-1] == 0)
    	{
    		maze[y][x-1] = temp+1;
    		cnt++;
    	}
    	if(x != sizex-1 && maze[y][x+1] == 0)
    	{
    		maze[y][x+1] = temp+1;
    		cnt++;
    	}
    	if(y != 0 && maze[y-1][x] == 0)
    	{
    		maze[y-1][x] = temp+1;
    		cnt++;
    	}
    	if(y != sizey-1 && maze[y+1][x] == 0)
    	{
    		maze[y+1][x] = temp+1;
    		cnt++;
    	}
    	return cnt;
    }
     
    int search_exit()
    {
    	int x, y;
    	exit.x = 0;
    	exit.y = 0;
    	y = 0;
    	for(x = 0; x!=sizex; x++)
    		if(maze[y][x] == 0)
    		{
    			exit.x = x;
    			exit.y = y;
    			return 1;
    		}
    	y = sizey-1;
    	for(x = 0; x!=sizex; x++)
    		if(maze[y][x] == 0)
    		{
    			exit.x = x;
    			exit.y = y;
    			return 1;
    		}
    	x = 0;
    	for(y = 0; y!=sizey; y++)
    		if(maze[y][x] == 0)
    		{
    			exit.x = x;
    			exit.y = y;
    			return 1;
    		}
    	x = sizex-1;
    	for(y = 0; y!=sizey; y++)
    		if(maze[y][x] == 0)
    		{
    			exit.x = x;
    			exit.y = y;
    			return 1;
    		}
    	return 0;
    }
     
    void print_maze(char mode)
    {
    	int x,y;
    	for(y = 0; y!=sizey; y++)
    	{
    		for(x = 0; x!=sizex; x++)
    		{
    			if(maze[y][x] == MEN)
    				cout << "M" << "";
    			else
    			if(mode == 1 && maze[y][x] == 0)
    				cout << "*" << "";
    			else
    			if(maze[y][x] > MEN)
    				cout << "0" << "";
    			else
    				cout << maze[y][x] << "";
    		}
    		cout << endl;
    	}
    }
     
    int main()
    {
    	int x, y, paths = 0, i = 1, steps, cnt = 0;
    	if(load_maze() == 0)
    	{
    		cout << "File maze.txt not found." << endl;
    		return 0;
    	}
    	//Вывод матрицы лабиринта в консоль:
    	cout << "Labirint:\r\n" << "(" << sizex << "x" << sizey << ")\r\n" << endl;
    	print_maze(ORIGINAL_MAZE);
    	//Легенда:
    	cout << "\r\nM - Chelovek\r\n1 - Stena\r\n0 - Prohod" << endl;
    	//Если нет граничного элемента, равного нулю, то выхода из лабиринта нет
    	if(search_exit() == 0)
    	{
    		cout << "\r\nVuhoda iz labirinta net." << endl;
    		return 0;
    	}
    	cout << "\r\nKoordinatu Vuhoda:\r\nX = " << exit.x << "; Y = " << exit.y << "\r\n" << endl;
    	//Ищем кратчайший путь к выходу из лабиринта:
    	while(1)
    	{
    		//Проходим по очереди все элементы матрицы и смотрим соседние элементы тех элементов, которые равны temp
    		for(y = 0; y!=sizey; y++)
    		{
    			for(x = 0; x!=sizex; x++)
    			{
    				if(maze[y][x] == temp)
    					paths += check(x,y); //Смотрим соседей элемента y,x
    			}
    		}
    		//paths равна нулю только если среди соседей элемента со значением temp нет ни одного
    		//элемента со значением 0 => человек замурован, завершить поиск пути.
    		if(paths == 0)
    		{
    			cout << "\r\nVuhoda iz labirinta net." << endl;
    			return 0;
    		}
     
    		paths = 0;
    		if(maze[exit.y][exit.x] == 0)
    			temp++;
    		else
    			break;
    	}
    	//Путь к выходу длиной steps:
    	steps = maze[exit.y][exit.x];
    	maze[exit.y][exit.x] = 0;
    	x = exit.x;
    	y = exit.y;
    	//Выделяем нулями пройденный путь:
    	while(1)
    	{
    		if(x != 0 && maze[y][x-1] == steps-i)
    		{
    			if(maze[y][x-1] == 2)
    				break;
    			maze[y][x-1] = 0;
    			x--;
    		}
    		if(x != sizex-1 && maze[y][x+1] == steps-i)
    		{
    			if(maze[y][x+1] == 2)
    				break;
    			maze[y][x+1] = 0;
    			x++;
    		}
    		if(y != 0 && maze[y-1][x] == steps-i)
    		{
    			if(maze[y-1][x] == 2)
    				break;
    			maze[y-1][x] = 0;
    			y--;
    		}
    		if(y != sizey-1 && maze[y+1][x] == steps-i)
    		{
    			if(maze[y+1][x] == 2)
    				break;
    			maze[y+1][x] = 0;
    			y++;
    		}
    		i++;
    	}
    	cout << "\r\nSimvol '*' - proydennuy element:\r\n" << endl;
    	print_maze(MAZE_WITH_PATH);
    	cout << "\r\nLabirint proyden za " << steps - 2 << " hodov " << endl;
    	return 1;
    }

    Матрица лабиринта находится в файле maze.txt в папке с .exe, кодировка файла ANSI. Элементы матрицы набираются через пробел. Пример:

    1_1_1_1_1

    1_2_1_0_0

    1_0_0_0_1

    1_1_0_1_1

    1_1_1_1_1

    Подчеркивание – это пробел.

    Скачать скомпилированный экзешник

     

    Понравилась статья? Нажмите на любую из кнопок:

    0
    Пока комментариев нет.

    :D :-) :( :o 8O :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen: