|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
06.03.2022, 19:36 | #1 |
Регистрация: 07.02.2022
Сообщений: 4
|
C#, шахматное поле с конями, ускорить выполнение кода
Мой код проходит первые тесты, но потом на вход идет 10000+ чисел и время превышает максимальное в 4 сек, как можно его ускорить?
Дано шахматное поле n × n . На поле расположено m коней. Определить, какое количество клеток не заняты и не находятся под боем. Формат ввода Первая строка входного файла содержит два числа n и m ( 1 ≤ n ≤ 1 0 0 0 , 1 ≤ m ≤ 5 0 0 0 0 ) – размеры поля и количество коней соответственно. Следующие m строк содержат пары координат x i , y i ( 1 ≤ x i , y i ≤ n ) – координаты очередного коня. Формат вывода Выведите одно число – ответ на задачу. Пример Ввод: 5 5 2 4 5 1 4 4 3 3 1 3 Вывод: 8 Код:
|
06.03.2022, 20:01 | #2 |
МегаМодератор
СуперМодератор
Регистрация: 09.11.2010
Сообщений: 7,318
|
Попробуйте вместо List использовать HashSet для точек.
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )
|
06.03.2022, 20:06 | #3 |
Форумчанин
Регистрация: 25.01.2015
Сообщений: 472
|
Можно попробовать так:
1. объявить матрицу n*n - M[n][n] 2. переменная - количество свободных полей Count=n*n 3. в цикле получать очередную координату (x, y) 4. если M[x][y]==2, то пропустить 5. иначе M[x][y]=2 (тут ещё проверить на ==1 и при равенстве 0 Count--) и проверить все точки, которые бьёт конь и если очередная точка ==0, то сделать её равной 1 и Count-- Т.е. матрица отслеживает два состояния - на этом месте стоит конь (чтобы повторно не рассматривать) и место "свободно" или "под боем". А учёт свободных полей вести отдельно, чтобы не пересматривать матрицу в конце. Может что-то пропустил - при реализации уточните. Можно обойтись и без контроля повторного использования поля - тогда можно использовать битовый массив, т.е. и размер памяти многократно уменьшится. |
07.03.2022, 00:23 | #4 |
Регистрация: 07.02.2022
Сообщений: 4
|
BDA, не помогло
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
C#, гонки на подах, ускорить выполнение кода | POrro | Помощь студентам | 2 | 05.03.2022 18:00 |
Sleep останавливает выполнение всего в программе а не задерживает выполнение конкретного куска кода? | Illusiony | Общие вопросы Delphi | 19 | 22.02.2015 18:37 |
Ускорить выполнение цикла | elen_7C9 | Общие вопросы C/C++ | 5 | 21.10.2012 22:06 |
Можно ли ускорить выполнение этого кода? | Velross | Помощь студентам | 3 | 07.01.2010 19:37 |
Можно ли как-то ускорить выполнение этого кода (обработка примечаний)? | motorway | Microsoft Office Excel | 2 | 23.07.2009 17:06 |