Форум программистов, компьютерный форум, киберфорум
C# Windows Forms
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
113 / 100 / 68
Регистрация: 21.04.2014
Сообщений: 1,420

Поиск всех возможных комбинаций букв в поле 5 на 5

29.03.2024, 13:23. Показов 790. Ответов 3
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте.
Пытаюсь реализовать игру "Балда" с полем 5 на 5. В качестве поля используется объект DataGridView. По моей задумке, алгоритм хода компьютера должен быть следующим:

1. Считаем сколько сейчас букв на поле.
2. Из нашей базы данных слов берём только те, чья длина равна количеству букв на поле + 1.
3. Составляем список всех возможных сочетаний из букв на поле (по диагонали не считаем) и сортируем его по уменьшению длины.
4. Проходимся по этому списку и к каждому элементу сначала слева, а потом справа подставляем все буквы алфавита по очереди и проверяем, получилось ли у нас одно из слов для словаря.
5. Если слово получилось, то записываем его в список возможных ответов и ищем дальше, но только среди слов такой же длины.
6. Из полученного списка возможных ответов случайным образом выбираем слово.

У меня проблема на пункте 3. Допустим, у нас начало игры и ходит компьютер. По центру записано слово "ОБЖИГ". Я хочу получить массив, содержащий следующий строки:
обжиг, обжи, обж, об, бо, бж, бжи, бжиг, жб, жбо, жи, жиг, иж, ижб, ижбо, иг, ги, гиж, гижб, гижбо.
Т.е. проверять надо каждую ячейку (начиная с 0, 3, потому что третья строка единственная в которую гарантировано вписано слово) на заполненность соседей, а потом переключаться на соседнюю и проверять уже для неё. Тут явно напрашивается какой-то рекурсивный метод, но у меня ничего подобного не выходит. Помогите, пожалуйста.

Добавлено через 42 минуты
Получилось родить нечто похожее, но увы, не работает как надо:

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
List<string> combinations = new List<string> ( );
 
for ( int i = 0; i < dgvPlayingField.Rows.Count; i++ )
{
    for ( int j = 0; j < dgvPlayingField.Columns.Count; j++ )
    {
        if ( dgvPlayingField.Rows [ i ].Cells [ j ].Value != null )
        {
            string currentCombination = "";
            GetContinuousCombinations ( i, j, currentCombination, combinations );
        }
    }
}
 
//...
 
 
private void GetContinuousCombinations ( int row, int col, string currentCombination, List<string> combinations )
{
    if ( row < 0 || row >= dgvPlayingField.Rows.Count || col < 0 || col >= dgvPlayingField.Columns.Count )
        return;
 
    if ( dgvPlayingField.Rows [ row ].Cells [ col ].Value == null )
        return;
 
    string cellValue = dgvPlayingField.Rows [ row ].Cells [ col ].Value.ToString ( );
    currentCombination += cellValue;
 
    combinations.Add ( currentCombination );
 
    // Рекурсивно проверяем соседние ячейки на наличие буквы
    GetContinuousCombinations ( row + 1, col, currentCombination, combinations ); // Вниз
    GetContinuousCombinations ( row - 1, col, currentCombination, combinations ); // Вверх
    GetContinuousCombinations ( row, col + 1, currentCombination, combinations ); // Вправо
    GetContinuousCombinations ( row, col - 1, currentCombination, combinations ); // Влево
}
Выход из рекурсии не происходит вовремя, currentCombination переполняется фигнёй =(
0
Лучшие ответы (1)
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
29.03.2024, 13:23
Ответы с готовыми решениями:

Замена несколько букв(генератор всех возможных комбинаций)
Привет,есть такая задача,имеем файл text где есть список слов,например word_list.txt в нем слова: scaner bmx forum еще...

Генерация всех возможных комбинаций слова путем манипуляций с регистрами букв
Привет всем! Появилась не стандартная задачка написать хитрый алгоритм. Вводим слово для примера газ (слово в нижнем регистре). ...

Вывод всех возможных комбинаций
Здравствуйте! Определена строка русским алфавитом, необходимо вывести все возможные комбинации слов для данного алфавита длиной 4, при этом...

3
2393 / 1922 / 763
Регистрация: 27.07.2012
Сообщений: 5,565
29.03.2024, 13:57
Цитата Сообщение от FaceHoof Посмотреть сообщение
Получилось родить нечто похожее, но увы, не работает как надо
Сначала надо бы словами описать само правило маршрута и выхода из рекурсии. Например:
1. Кладём текущую ячейку в буфер
2. Выбираем направление (вверх, направо, вниз, налево)
3. Проверка, есть ли по выбранному направлению ячейка с буквой и не были ли мы уже на ней
4. Если да - идём на пункт 1 с выбранной ячейкой
5. Если нет, то выводим содержимое буфера, удаляем текущую ячейку из буфера. Конец рекурсии

Набросал интуитивно, надо проверять.

Добавлено через 11 минут
Ну и конечно же, игровое поле придётся делать отдельным двумерным массивом структур, содержащих информацию о букве в ячейке и признаке обхода её (и может что ещё). А DataGridView должна просто отображать состояние этого массива.
1
113 / 100 / 68
Регистрация: 21.04.2014
Сообщений: 1,420
02.04.2024, 13:16  [ТС]
Начал писать алгоритм с нуля и у меня почти получилось!
Для проверки, посещалась ли ячейка, я использую список посещённых ячеек. Так как направления движения всего 4, то я сделал массив возможных смещений.

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
75
private List<string> lstAllPos = new List<string> ( ); //Список доступных на поле комбинаций букв
private string strCur = string.Empty; //Текущая строка, для добавления в lstAllPos
 
 
//...
 
 
private void CompTurn ( )
{
    lstAllPos.Clear ( );
 
    // Проходим по всем клеткам dataGridView
    for ( int row = 0; row < dgvPlayingField.Rows.Count; row++ )
    {
        for ( int col = 0; col < dgvPlayingField.Columns.Count; col++ )
        {
            DataGridViewCell cell = dgvPlayingField [ col, row ];
 
            // Проверяем, содержит ли клетка букву
            if ( cell.Value != null )
            {
                ProcessCell ( cell, new List<DataGridViewCell> ( ) );
                strCur = string.Empty;
            }
        }
    }
}
 
private void ProcessCell ( DataGridViewCell cell, List<DataGridViewCell> visited )
{
    // Если клетка уже посещена, выходим из метода, чтобы избежать зацикливания
    if ( visited.Contains ( cell ) )
        return;
 
    // Добавляем текущую клетку в список посещенных
    visited.Add ( cell );
 
    // Если значение в клетке равно null, выходим из метода
    if ( cell.Value == null )
        return;
 
    // Добавляем значение клетки в список lstAllPos
    strCur += cell.Value.ToString ( );
    lstAllPos.Add ( strCur );
 
    // Проверяем соседние клетки
    foreach ( DataGridViewCell neighborCell in GetNeighborCells ( cell ) )
    {
        // Рекурсивно обрабатываем соседнюю клетку
        ProcessCell ( neighborCell, new List<DataGridViewCell> ( visited ) );
    }
}
 
private IEnumerable<DataGridViewCell> GetNeighborCells ( DataGridViewCell cell )
{
    int row = cell.RowIndex;
    int col = cell.ColumnIndex;
 
    // Массив смещений для получения соседних клеток
    int [ , ] offsets = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };
 
    // Перебираем соседние клетки
    for ( int i = 0; i < 4; i++ )
    {
        int newRow = row + offsets [ i, 0 ];
        int newCol = col + offsets [ i, 1 ];
 
        // Проверяем, не вышли ли мы за пределы dgvPlayingField
        if ( newRow >= 0 && newRow < dgvPlayingField.Rows.Count &&
            newCol >= 0 && newCol < dgvPlayingField.Columns.Count )
        {
            yield return dgvPlayingField [ newCol, newRow ];
        }
    }
}
Это уже очень близко к тому, что я хочу. Но всё ещё есть критичная ошибка: переменную strCur надо обнулять не только при смене отправной ячейки, но и при смене направления.
Поясню на том же слове "ОБЖИГ" вписанному по центру: Мы отлично отрабатываем с буквой "О" и получаем все нужные комбинации. Но когда доходим до "Б", то получаем список из "Б", "БО", "БОЖ"... Вот этого "БОЖ" уже быть не должно, разумеется, должно быть "БЖ". Вроде бы и понятно что надо сделать, но чёт я на удивление долго с этим туплю...

И да, согласен, что было бы куда правильнее использовать двумерный массив и не заморачиваться с самим объектом DataGridView. Но как бы это смешно не звучало, я чёт слишком увлёкся, чтобы подумать об этом заранее ¯\_(ツ)_/¯ Теперь уже хочется увидеть, что всё работает, а потом на двумерный массив переходить...
0
2393 / 1922 / 763
Регистрация: 27.07.2012
Сообщений: 5,565
02.04.2024, 14:41
Лучший ответ Сообщение было отмечено FaceHoof как решение

Решение

FaceHoof, я в прошлый раз не скинул вам свой пример, который на коленке писал: https://dotnetfiddle.net/CnLh3Y

Кликните здесь для просмотра всего текста
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
using System;
using System.Text;
                    
public class Program
{
    public static void Main()
    {
        string word = "обжиг";
        for (int i = 0; i < word.Length; ++i)
        {
            MapMe(word, i, i, new StringBuilder());
        }
    }
    
    private static void MapMe(string word, int index, int from, StringBuilder sb)
    {
        sb.Append(word[index]);
        if (index < word.Length - 1 && from != index + 1)
            MapMe(word, index + 1, index, sb);
        if (index > 0 && from != index - 1)
            MapMe(word, index - 1, index, sb);
        if (sb.Length > 1)
            Console.WriteLine(sb);
        sb.Remove(sb.Length - 1, 1);
    }
}
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
обжиг
обжи
обж
об
бжиг
бжи
бж
бо
жиг
жи
жбо
жб
иг
ижбо
ижб
иж
гижбо
гижб
гиж
ги


Там только одномерная строка, поэтому не очень информативно. Однако ваш случай обходит.

Добавлено через 43 минуты
FaceHoof, хотя двумерный вариант при наличии указанного выше массива ячеек не намного сложнее: https://dotnetfiddle.net/RVnCJA

Кликните здесь для просмотра всего текста
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
using System;
using System.Text;
 
class Cell
{
    public bool IsUsed { get; set; }
    public char Letter { get; set; }
    public bool HasLetter { get { return Letter != '.'; } }
}
                    
public class Program
{
    public static void Main()
    {
        char[,] rawField = new char[5, 5] {
            { '.', '.', '.', '.', '.' },
            { '.', 'о', '.', '.', '.' },
            { '.', 'б', 'ж', 'и', '.' },
            { '.', '.', '.', 'г', '.' },
            { '.', '.', '.', '.', '.' }
        };
        
        Cell[,] field = new Cell[5, 5];
        for (int i = 0; i < 5; i++)
        {
            for (int j = 0; j < 5; j++)
                field[i, j] = new Cell { Letter = rawField[i, j] };
        }
        
        for (int i = 0; i < field.GetLength(0); i++)
        {
            for (int j = 0; j < field.GetLength(1); j++)
            {
                MapMe(field, i, j, new StringBuilder());
            }                    
        }
    }
    
    private static void MapMe(Cell[,] field, int x, int y, StringBuilder sb)
    {
        if (!field[x, y].HasLetter)
            return;
        
        sb.Append(field[x, y].Letter);
        field[x, y].IsUsed = true;
        
        // go up
        if (y > 0 && !field[x, y - 1].IsUsed && field[x, y - 1].HasLetter)
            MapMe(field, x, y - 1, sb);
        // go right
        if (x < field.GetLength(0) - 1 && !field[x + 1, y].IsUsed && field[x + 1, y].HasLetter)
            MapMe(field, x + 1, y, sb);
        // go down
        if (y < field.GetLength(1) - 1 && !field[x, y + 1].IsUsed && field[x, y + 1].HasLetter)
            MapMe(field, x, y + 1, sb);
        // go left
        if (x > 0 && !field[x - 1, y].IsUsed && field[x - 1, y].HasLetter)
            MapMe(field, x - 1, y, sb);
        
        field[x, y].IsUsed = false;
        if (sb.Length > 1)
            Console.WriteLine(sb);
        sb.Remove(sb.Length - 1, 1);
    }
}
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
обжиг
обжи
обж
об
бжиг
бжи
бж
бо
жбо
жб
жиг
жи
ижбо
ижб
иж
иг
гижбо
гижб
гиж
ги
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
02.04.2024, 14:41
Помогаю со студенческими работами здесь

Генератор всех возможных комбинаций
Нужно написать генератор всех возможных комбинаций, допустим состоящих из 2-х, 3-х, 4-х символов и сохраняющих комбинации в файл, вот...

Сортировка всех возможных комбинаций 4 из 8
Задача состоит в том, что бы сложить 4 элемента массива, который состоит из 8 элементов, во всех возможных комбинациях int array; //...

Генерация всех возможных комбинаций
Доброго времени суток, подскажите идею, нужно чтобы функция составила все возможные комбинации из цифр и английских букв.

Перебор всех возможных комбинаций
Доброго дня. Есть задание, написать брутфорс, по заданному алфавиту. То что представлено ниже, вроде успешно работает, но с 1...

Генератор всех возможных комбинаций строки
Помогите сделать генератор ВСЕХ значений видов: CBCCB BCCBC Где: C - цифры(2-9) B - буквы(A-Z) - большие! То-есть мне надо все...


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Новые блоги и статьи
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора
ФедосеевПавел 14.03.2026
Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию
anaschu 13.03.2026
прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru