а весом рёбер будет выступать расстояние между этими полями. для того чтобы после построения этого графа выбрать в нём 2 вершины и найти между ними кратчайший путь ... Двигаться по карте можно только по горизонтали и по вертикали.
Это какой-то бред. Начало фразы подразумевает, что ребра есть между всеми парами вершин, продолжение говорит, что все ребра длины 1 между соседними клетками. Я предполагаю что тут именно второй вариант.
Во-первых, занумеруйте все клетки. Подойдет простая формула вроде
i+m*j
Вот у вас уже есть
n*m вершин в графе. Теперь добавьте ребра. Для каждой клетки (два цикла) посмотрите 4 соседние клетки. Если обе клетки -
., то добавьте из текущей клетки ребро в соседнюю.
Соседей удобно перебирать, если завести константные массивы для смещений:
const int dx[4]= {1, 0, -1, 0};
const int dy[4]= {0, 1, 0, -1};
Тогда для клетки
(i, j) можно перебрать всех соседей одним циклом на 4 итерации -
(i+dx[k], j+dy[k]). Надо только не забыть проверить на выход за границы матрицы.
Ну и вам надо написать функцию типа
AddEdge(int u, int v) которая будет в удобную для вас структуру данных добавлять ребра. Граф удобно хранить в виде списков смежности. На C++ это можно сделать просто
std::vector<std::vector<int>> и добавлять соседей через
vector::push_back. Это на практике работает быстрее всяких связных списков.
И у вас будет три вложенных цикла - внешние по всем клеткам, а внутренний по четырем направлениям. Внутри вы проверяете, что сосед по этому направлению есть и между клетками можно пройти. В этом случае вызывайте AddEdge.
А можно вообще граф не строить. Берете ваш алгоритм поиска кратчайшего пути (BFS, Dijkstra или A*) и там везде, где перебираются соседи одной вершины, вставляете код проверки четырех направлений через dx/dy. Вершины можно или нумеровать их координатами, и тогда все массивы пометок будут двумерными, или можно использовать формулу
u = i+j*m, (i,j) = (u%m, u/m) для преобразования координат в номер вершины и назад.
А еще есть всякие алгоритмы, которые работают сильно быстрее за счет использования того факта, что у вас не произвольный граф, а сетка в матрице.
Jump Point Search - один из таких алгоритмов. В нем граф умышленно не строится и работа идет непосредственно в матрице.
