Форум программистов, компьютерный форум CyberForum.ru

Волновой алгоритм для двумерной матрицы - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Заменить заданный столбец матрицы а на вектор b http://www.cyberforum.ru/cpp-beginners/thread689157.html
Дана квадратная матрица a размерностью 5х5 и вектор b размерностью 5. Заменить заданный столбец матрицы a на вектор b. Номер столбца матрицы a вводить с клавиатуры. Матрицу и вектор инициализировать в программе.
C++ Характеристикой строки целочисленной матрицы назовем сумму её положительных четных элементов Характеристикой строки целочисленной матрицы назовем сумму её положительных четных элементов. Переставляя строки заданной матрицы, расположить их в соответствии с ростом характеристик. Вот начало: #include <iostream> int main() { http://www.cyberforum.ru/cpp-beginners/thread689148.html
C++ написать программу вычисляющую значение матричного выражения C=2(A+B)B
-ввод массивов организовать в функции main() -Сумму массивов, произведение массивов и умножение массива на число организовать в отдельных ф-циях -Печать массива С организовать в функции main() Помоите , пожалуста . Зарание огромное спасибо.
C++ Быстрая Сортировка quick-sort (ошибка в 40 строке) как исправить?
#include <iostream> #include <vector> using std::endl; using std::cout; using std::vector; template<class T> void print_vector( vector<T>& v); template<class T> void prepare_vector(vector<T>* v);
C++ Найти сумму элементов численного массива http://www.cyberforum.ru/cpp-beginners/thread689138.html
#include "stdafx.h" #include <iostream> #include <conio.h> using namespace std; #include "stdafx.h" #include <iostream> #include <conio.h> int i; using namespace std;
C++ Вычислить Z = (S1 + S2)/ 2 Вычислить Z = (S1 + S2)/ 2; где S1 сумма положительных элементов массива X(9x6), а S2 - сумма отрицательных элементов массива А(60).Суммы вычислять в одной функции. Не могу понять в чём ошибка... #include <iostream> #include <fstream> #define SIZE_i 9 #define SIZE_j 6 #define SIZE_A 60 #define N 2 подробнее

Показать сообщение отдельно
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
05.11.2012, 17:20     Волновой алгоритм для двумерной матрицы
Цитата Сообщение от !Андрей! Посмотреть сообщение
а моете пожалуйста подсказать как реализовать поиск правильно?
Пока напишу сам волновой алгоритм. Допустим дана матрица (карта):
#######
#_____#
#_G___#
#____S#
#######
Создаете такую же размерами типа int (все элементы равны 0):
0000000
0000000
0000000
0000000
0000000
Далее все изменения будут только в этой матрице.
Элементу который соответствует G ставите 1. И заносите его в очередь. Т.е. в очереди изначально будет элемент с координатами (2,2) (индексация элементов с нуля).
Теперь пока очередь не опустеет (или можно делать пока элемент матрицы соответствующий S во втором массиве равен 0) делаете так:
Берете очередной элемент из очереди. Если сверху элемент равен 0 и в первом массиве элемент с этими координатами не равен #, то заносите в очередь элемент сверху, во втором массиве ставите ему значение на 1 больше чем значение только что взятого элемента из очереди. Тоже самое для элементов слева, справа, снизу.
В общем если рассматривать волны, то второй массив будет меняться так:
1 волна.
0000000
0000000
0010000
0000000
0000000
2 волна.
0000000
0020000
0212000
0020000
0000000
3 волна.
0000000
0323000
0212300
0323000
0000000
4 волна.
0000000
0323400
0212340
0323400
0000000
5 волна.
0000000
0323450
0212340
0323450
0000000
здесь останавливаемся, т.к. элемент где стоит S уже не равен 0. Сам путь теперь вычисляем так. Берем значение во втором массиве где стоит S. Это значение 5.
Пока это значение не станет равнным 1, делаем так:
Ищем из всех рядом стоящих значений значение на 1 меньше и переходим туда (можно помечать путь в первом масиве), уменьшая наше значение на 1.
 
Текущее время: 11:11. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru