Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.92/13: Рейтинг темы: голосов - 13, средняя оценка - 4.92
0 / 0 / 0
Регистрация: 10.06.2015
Сообщений: 2

Определение существования пути в двумерном массиве

11.06.2015, 21:17. Показов 2449. Ответов 2
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте, нужна помощь. Есть двумерный квадратный массив размерностью от 8х8 до 32х32.
Например:
---12345678---
1 {00004507}
2 {10023004}
3 {00345000}
4 {00221100}
5 {10531000}
6 {50000000}
7 {00000000}
8 {04620053}
Ненулевой элемент - объект. Нулевой элемент - пустое место. Сквозь пустые места есть путь. По диагонали перемещать элементы нельзя.
Нужно проверить, можно ли переместить ненулевой элемент в свободное место.
Например, выбираем элемент [1, 2] (единичка в массиве) и проверяем, можно ли переместить его в пустую клетку [7, 1]. Если можно, возвращаем значение true. Если нет - false.

Нужно разработать метод, который будет возвращать значение "true" или "false". На вход метод получает массив, точку начала пути и точку, в которую нужно прийти.
Что-то вроде:
C#
1
public bool WayIsClear(int[,] field, int fromX, int fromY, int toX, int toY)
Эффективность и скорость работы алгоритма не имеет значения. Чем проще, тем лучше.

Читал про А*, поиск в ширину, алгоритм Дейкстры - вроде понятен принцип работы, но реализовать не получается.
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
11.06.2015, 21:17
Ответы с готовыми решениями:

Поиск пути в двумерном массиве (не про Дийкстру)
Есть булевый двумерный массив. Путь - это последовательность столбцов записанных в одномерный массив. Путь строится от первой строки к...

Рекурсия поиска кратчайшего пути в двумерном массиве
пример массива (ходить можно только по точкам, S- начало, F- конец) # # # # # # # # # # # . . . . . . . . # # . # . # . # . . # ...

Поиск пути для одинаковых элементов в двумерном массиве
в общем у меня есть матрица и там есть элементы равным 1 а все остальные равны нулю, как найти путь от одного к остальным, какой поиск...

2
Эксперт .NETАвтор FAQ
 Аватар для Storm23
10427 / 5157 / 1825
Регистрация: 11.01.2015
Сообщений: 6,226
Записей в блоге: 34
11.06.2015, 21:49
Spmart,
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
using System;
using System.Collections.Generic;
using System.Linq;
 
namespace ConsoleApplication196
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = @"
00004507
10023004
00345000
00221010
10531001
50000000
00000000
04620053";
            var field = new int[8,8];
            //init
            var lines = s.Split(new char[] {'\r', '\n'}, StringSplitOptions.RemoveEmptyEntries);
            for (int j = 0; j < field.GetLength(1); j++)
            for (int i = 0; i < field.GetLength(0); i++)
                field[j, i] = int.Parse(lines[j][i].ToString());
            //find
            var hasWay = WayIsClear(field, new Point{X = 0, Y = 1}, new Point{X = 6, Y = 0});
            //
            Console.WriteLine(hasWay);
            Console.ReadLine();
        }
 
        public static bool WayIsClear(int[,] field, Point from, Point to)
        {
            var hash = new HashSet<Point>();
            //
            var temp = field[from.Y, from.X];
            field[from.Y, from.X] = 0;
            //
            var res = WayIsClear(field, from, to, hash);
            //
            field[from.Y, from.X] = temp;
            //
            return res;
        }
 
        private static bool WayIsClear(int[,] field, Point from, Point to, HashSet<Point> hash)
        {
            if (hash.Contains(from)) return false;
            if (!WithInField(field, from)) return false;
            if (field[from.Y, from.X] != 0) return false;
            if (from.Equals(to)) return true;
 
            hash.Add(from);
 
            return WayIsClear(field, new Point() {X = from.X + 1, Y = from.Y}, to, hash) ||
                   WayIsClear(field, new Point() {X = from.X - 1, Y = from.Y}, to, hash) ||
                   WayIsClear(field, new Point() {X = from.X, Y = from.Y + 1}, to, hash) ||
                   WayIsClear(field, new Point() {X = from.X, Y = from.Y - 1}, to, hash);
 
        }
 
        static bool WithInField(int[,] field, Point p)
        {
            return p.X >= 0 && p.X < field.GetLength(1) && p.Y >= 0 && p.Y < field.GetLength(0);
        }
    }
 
    struct Point
    {
        public int X;
        public int Y;
    }
}
2
0 / 0 / 0
Регистрация: 10.06.2015
Сообщений: 2
11.06.2015, 22:22  [ТС]
Спасибо за быстрый отклик.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
11.06.2015, 22:22
Помогаю со студенческими работами здесь

Поиск пути в двумерном массиве методом "в ширину"
Все что имею: Двумерный массив, заполненный нулями(стенками) и единицами(пустотой). Положение игрока X и Y. И положение цели, X0 и Y0. ...

Проверка существования файла по указанному пути
Скажите пожалуйста как сделать так что бы....Пример: при нажатии на кнопку у меня скачивается файл в мою дерикторию но если файл там уже...

Определение существования папки
Помогите, пожалуйста! Как определить, существует ли директория с заданным именем в текущей директории? Как я понимаю, с помощью Dir?

Определение существования переменнной
Вобщем у меня есть массив объектов моего класса и нужно определить, инициализирован ли элемент, стоящий на определенной позиции в массиве....

Найти вероятность существования пути в графе между заданными точками
Запутался в рекурсии. Смысл задачи: найти вероятность существования пути в графе между заданными точками. Смысл функции gen() на данном...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru