Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/9: Рейтинг темы: голосов - 9, средняя оценка - 4.67
56 / 56 / 29
Регистрация: 21.09.2009
Сообщений: 313
Записей в блоге: 1
1

"Буквенный" лабиринт (TopCoders 250)

13.11.2011, 11:23. Показов 1801. Ответов 7
Метки нет (Все метки)

Хотелось бы узнать ваш алгоритм решения это задачи .
Дан массив string[] letterMaze , состоящий из строк, содержащх буква английского алфавита [A-Z] или точки на тех местах, где нет букв. В массиве каждая буква встречается только один раз. Массив содержит до 50 строк, каждая из которых не более 50 символов длинной.
Нужно определить, можно ли проложить "алфавитный путь" от буквы 'A' до 'Z'.
"Aлфавитный путь" это последовательность 26 букв английского алфавита , таких , что :
- Первая буква - А.
- Вторая буква ( B ) находится горизонтально слева (или справа) или вектикально сверху(или синзу) от буквы А.
- Третья буква ( С ) находится горизонтально слева (или справа) или вектикально сверху(или синзу) от буквы В.
- .............
-Последняя буква - Z.

Например :
C#
1
string[] letterMaze = new string [] {"ABCDEFGHIJKLMNOPQRSTUVWXYZ"}
Возвращает "Да"
C#
1
string[] letterMaze = new string [] {"ACBDEFGHIJKLMNOPQRSTUVWXYZ"}
Возвращает "Нет"
C#
1
2
3
4
5
6
7
8
9
10
11
string[] letterMaze = new string [] {"..............",
 "..............",
 "..............",
 "...DEFGHIJK...",
 "...C......L...",
 "...B......M...",
 "...A......N...",
 "..........O...",
 "..ZY..TSRQP...",
 "...XWVU.......",
 ".............."}
Возвращает "Да"
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.11.2011, 11:23
Ответы с готовыми решениями:

Известны сорта роз, выращиваемых тремя цветоводами: "Анжелика", "Виктория", "Гагарин", "Ave Maria", "Катарина", "Юбилейн
Известны сорта роз, выращиваемых тремя цветоводами: "Анжелика", "Виктория", "Гагарин", "Ave...

Дан массив строк: "red", "green", "black", "white", "blue". Запишите в файл элементы массива построчно (в новой строке)
пишу так но не помогает: static void Main(string args) { string...

Игра "Лабиринт". Отделить логику от интерфейса
Привет всем, извините за возможно глупый вопрос, но что значит отделить логику от интерфейса. Пишу...

Описать класс "поезд", содержащий поля "пункт назначения", "номер поезда", "время отправления"
Помогите пожалуйста с классом Описать класс «поезд», содержащий следующие закрытые поля:...

7
Эксперт .NET
15449 / 11712 / 3076
Регистрация: 17.09.2011
Сообщений: 19,603
13.11.2011, 11:47 2
Как правило, в таких задачках выкладывают требование по времени выполнения, иначе можно все проверить простым перебором.
А к требованию по времени хотелось бы получить несколько вариантов входных данных для проверки, желательно 50х50 с наличием пути и без.
0
56 / 56 / 29
Регистрация: 21.09.2009
Сообщений: 313
Записей в блоге: 1
13.11.2011, 12:23  [ТС] 3
Ограничений по времени в тексте задания я не увидел. Но согласитесь, решать перебором - не лучший вариант. Мне просто хочется узнать алгоритмы решения этой задачи. =
Мое решение :
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
 class CountingSeries
    {
        public string doesItExist(string[] letterMaze)
        {
            char[,] array = new char[50, 50];
            string element = "";
            int x_pozition = 0, y_pozition = 0,counter = 2, j = 0 , total = 1;
            string letters = " ABCDEFGHIJKLMNOPQRSTUVWXYZ";
         
            
            for (int i = 1; i <= letterMaze.Length; i++)
                for (j = 1; j <= letterMaze[i-1].Length; j++)
                {
                    element = letterMaze[i-1];
                    array[i, j] = element[j-1];
                    if (element[j-1] == 'A') { x_pozition = j; y_pozition = i; }
                }
    
                label :
            for (int i = y_pozition - 1; i <= y_pozition + 1; i++)
                for (j = x_pozition - 1; j <= x_pozition + 1; j++)
                    {
                        if (total > 25) break;
                        if (array[i, j] == letters[counter] && ( (Math.Abs(x_pozition -j) + Math.Abs(y_pozition -i))==1))
                        {
                            total++;
                            counter++;
                            x_pozition = j;
                            y_pozition = i;
                            goto label; 
                        }
                    }
                
            if ( total == 26) return "YES";
            else return "NO";
        }  
    }
0
Эксперт .NET
15449 / 11712 / 3076
Регистрация: 17.09.2011
Сообщений: 19,603
13.11.2011, 13:05 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
static bool Solve(string[] maze)
{
    int x = -1, y = -1;
    for (int i = 0; i < maze.Length && y == -1; i++) {
        y = maze[i].IndexOf('A');
        x = i;
    }
    if (y == -1) return false;
 
    char next = 'A';
    while (next++ != 'Z') {
        if (y > 0 && maze[x][y - 1] == next)
            --y;
        else if (y < maze[x].Length - 1 && maze[x][y + 1] == next)
            ++y;
        else if (x > 0 && maze[x - 1][y] == next)
            --x;
        else if (x < maze.Length - 1 && maze[x + 1][y] == next)
            ++x;
        else
            return false;
    }
    return true;
}
На данный момент путь в лабиринте 50х50, где буквы расположены в самом худшем из возможных вариантов (А находится в конце последней строчки и все последующие буквы расположены так, что выполняется только последнее или предпоследнее условия), высчитывается за 0.8мс, включая вывод результата в консоль.

Есть пара мыслей по оптимизации:
1. Изначально искать не букву А, а любую букву, после чего запустить два потока, где первый будет идти на уменьшение до А, а второй - на увеличение до Z.
2. Распараллелить цикл поиска изначальной буквы, чтобы каждый поток искал в определенной части лабиринта.

Добавлено через 7 минут
Попробовал ваш код - выдает IndexOutOfRangeException на вот этой строчке:
C#
1
array[i, j] = element[j - 1];
1
56 / 56 / 29
Регистрация: 21.09.2009
Сообщений: 313
Записей в блоге: 1
13.11.2011, 18:34  [ТС] 5
Спасибо. У меня еще один вопрос, новую тему создавать не буду - задам тут:
Можете объяснить, как работает этот код?
C#
1
2
IEnumerable<int> flatMatrix = array.Cast<int>().ToList();
            int max = flatMatrix.Where(n => flatMatrix.Count(x => x == n) >= 2).Max();
0
Эксперт .NET
15449 / 11712 / 3076
Регистрация: 17.09.2011
Сообщений: 19,603
13.11.2011, 18:39 6
Находит максимальное из чисел, встречающихся в коллекции более одного раза.

Непонятно, правда, зачем ее к списку приводят.
0
56 / 56 / 29
Регистрация: 21.09.2009
Сообщений: 313
Записей в блоге: 1
13.11.2011, 19:54  [ТС] 7
Не знаю, я просто нашел код. А как объяснить, как этот код работает; что происодит во время его выполнения? Первая строка приводит исходный массив к списку, а вторая?
C#
1
(n => flatMatrix.Count(x => x == n) >= 2)
Что происходит в этом выражении?
0
Эксперт .NET
15449 / 11712 / 3076
Регистрация: 17.09.2011
Сообщений: 19,603
13.11.2011, 20:20 8
Для каждого n проверяется сколько раз он встречается в массиве и если более одного раза, данный элемент используется итератором при обходе результата.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.11.2011, 20:20

Построить иерархию классов "Студент", "преподаватель", "персона", "заведующий кафедрой"
Построить иерархию классов: Студент, преподаватель, персона, заведующий кафедрой 1) Разработать...

Методом вычислить тип треугольника: "не существует", "тупоугольный", "прямоугольный", "остроугольный"
Помогите пожалуйста С помощью метода вычислить тип треугольника::cry: 1) если первый параметр...

Проблема при сравнении: "Оператор ">" не может применяться к операндам типа "Т" и "Т""
Добрый день , пишу сортировку , все делаю на основе Т , но вот в чем проблемма public class...

приложение "лабиринт"
Доброго времени суток! Хочу реализовать приложение &quot;лабиринт&quot;, которое будет иметь два выхода, и...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.