Поиск «следа» в двумерных матрицах размеров

Question

Я не знаю, как понять этот вопрос, я всего лишь новичок в информатике.

Ввод будет представлять собой 2D-массив A [n] [n] чисел, представляющий топографическую карту географической поверхности. Также среди входных данных будет начальное местоположение (r, c). ссылаясь на запись A [r] [c]

Если вы планировали туристические маршруты, вы были бы связаны различиями в высоте между соседними записями. Человек может пересекать 2 соседних места, если их возвышения отличаются не более чем на 2). Примыкание следует только 4 стандартным направлениям компаса (так что я не предполагаю никаких диагоналей). Следовательно, точка на карте считается достижимой, если она пересекается с A [r] [c] через любую последовательность смежных объектов.

Напишите алгоритм, который вычисляет все доступные местоположения. Результатом будет другой 2D-массив R [n] [n] с значениями true/fals. (Я предполагаю, что это означает, что доступный, ложный означает недостижимый)

Если я правильно понял этот вопрос, я могу создать следующую матрицу. (Предположу, A [10] [10] выглядит следующим образом от A [0] [0] :)

50 51 54 58 60 60 60 63 68 71 
48 52 51 59 60 60 63 63 69 70 
44 48 52 55 58 61 64 64 66 69 
44 46 53 52 57 60 60 61 65 68 
42 45 50 54 59 61 63 63 66 70 
38 42 46 56 56 63 64 61 64 62 
36 40 44 50 58 60 66 65 62 61 
36 39 42 49 56 62 67 66 65 60 
30 36 40 47 50 64 64 63 62 60 
50 50 50 50 50 50 50 50 50 50 

И на юг и восток находится проходимые от A [0] [0] так достижимые записи будут:

50 51 54 58 60 60 60 63 68 71 
48 52 51 59 60 60 63 63 69 70 
44 48 52 55 58 61 64 64 66 69 
44 46 53 52 57 60 60 61 65 68 
42 45 50 54 59 61 63 63 66 70 
38 42 46 56 56 63 64 61 64 62 
36 40 44 50 58 60 66 65 62 61 
36 39 42 49 56 62 67 66 65 60 
30 36 40 47 50 64 64 63 62 60 
50 50 50 50 50 50 50 50 50 50 

так что я могу сделать вывод, что мой полученный массив должен быть

1 1 0 0 0 0 0 1 0 0 
1 1 1 0 0 0 1 1 0 0 
0 0 1 0 0 0 1 1 1 0 
0 0 1 1 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 1 0 
0 0 0 1 1 0 0 0 1 1 
0 0 0 0 1 1 0 0 1 1 
0 0 0 0 1 1 0 0 0 1 
0 0 0 0 0 1 1 1 1 1 
0 0 0 0 0 0 0 0 0 0 

Наш профессор просят нас осуществить это в псевдокоде. Я не знаю, как делать сравнения для двух соседних точек и четырех направлений точки. Кто-нибудь может дать мне некоторые идеи?

Answer 1

Это просто наводнение. Вам нужна очередь и индекс-адресуемый вектор «посещенных» флагов. Поместите корень в очередь. Вист, что очередь не пуста, возьмите первый элемент и проверьте доступные места N, S, E, W. Затем проверьте, были ли они посещены. Если нет, пометьте их как посещенные и поместите их в очередь.