Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Effsus
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 16
#1

Найти кратчайший путь шахматного короля - C++

15.10.2016, 18:27. Просмотров 421. Ответов 15
Метки нет (Все метки)

Здравствуйте, имеется задача:
Есть шахматное поле NxM
N, M ≤ 10^9
На шахматном поле отмечено два прямоугольника размерами не менее 1х1.
Нужно найти кратчайший путь короля из первого прямоугольника во второй.
Можно ходить в любую сторону.
Каким алгоритмом лучше всего это будет реализовать?

Добавлено через 1 час 50 минут
Up.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.10.2016, 18:27
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти кратчайший путь шахматного короля (C++):

Как найти кратчайший путь в лабиринте? - C++
Чтобы найти кратчайший путь в лабиринте использую волновой алгоритм, его сделал, но вот кратчайший путь не получается восстановить. ...

Найти кратчайший путь из вершины u в вершину v - C++
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Найти самый кратчайший путь в массиве - C++
У меня есть динамический массив в котором количество строк задаётся при выполнении программы, а количество строк неизменно и равно 3. Мне...

Как найти НЕ Кратчайший путь в графе ? - C++
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан списком смежности типа: 5 1 1 2 3...

С помощью метода волны найти кратчайший путь из одной клетки в другую (ход конём) - C++
Пытаюсь решить такую задачу: с помощью метода волны нужно найти кратчайший путь из одной клетки в другую. Проблема состоит в том, что я...

Найти кратчайший путь в лабиринте, который представлен в виде составного куба заданного размера - C++
Найти кратчайший путь в лабиринте, который представлен в виде составного куба NxNxN, состоящего из маленьких кубиков. Все кубики...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Nosey
1348 / 399 / 107
Регистрация: 22.10.2014
Сообщений: 861
Завершенные тесты: 2
15.10.2016, 18:59 #2
Effsus, А ещё преграды у короля есть? Или он один играет в шахматы?
Если один - то "век воли не видать - по диагонали ходи, а потом по прямой".
Если же не один, то тут сложно и "ваши слова недостаточно мотивируют, и моя лень таки побеждает".
0
Effsus
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 16
15.10.2016, 19:19  [ТС] #3
Преград нету.

Добавлено через 1 минуту
Но условия, чтобы код выполнялся менее, чем за 0.1 секунды.
0
Nosey
1348 / 399 / 107
Регистрация: 22.10.2014
Сообщений: 861
Завершенные тесты: 2
15.10.2016, 19:30 #4
Цитата Сообщение от Effsus Посмотреть сообщение
Преград нету.
А наработки есть? И зачем вам, решать такую задачу?

Цитата Сообщение от Effsus Посмотреть сообщение
На шахматном поле отмечено два прямоугольника размерами не менее 1х1.
А с какой позиции в этом прямоугольнике король должен начать путь? В любой?
0
Effsus
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 16
15.10.2016, 19:54  [ТС] #5
Были наработки, связанные с вашим предложением: ходить по диагонали, если нужно и можно, а потом по прямой, но код работал слишком долго из-за того, что перебирались все позиции. Да, король может начать в любой части прямоугольника. Нужно вычислить минимальное кол-во ходов, нужное, чтобы король добрался из одного прямоугольника во второй.

Добавлено через 7 минут
Решаю задачи для получения опыта. Но с этой задачкой возникли трудности
0
Новичок
Модератор
1207 / 778 / 173
Регистрация: 17.07.2012
Сообщений: 4,202
Записей в блоге: 1
Завершенные тесты: 2
15.10.2016, 20:16 #6
Цитата Сообщение от Effsus Посмотреть сообщение
Нужно вычислить минимальное кол-во ходов, нужное, чтобы король добрался из одного прямоугольника во второй.
Вот с этого и надо было начинать. Потому что найти путь за 0.1 секунду при таких ограничениях нереально, а длину можно. Но все равно какое-то странное условие. Можете примеры тестов привести(с объяснениями желательно)?
Цитата Сообщение от Effsus Посмотреть сообщение
Нужно найти кратчайший путь короля из первого прямоугольника во второй.
Зависит же еще от того где король стоит.
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
15.10.2016, 20:27 #7
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
76
77
78
79
80
81
82
83
84
//Есть шахматное поле NxM
//N, M ≤ 10^9
//На шахматном поле отмечено два прямоугольника размерами не менее 1х1.
//Нужно найти кратчайший путь короля из первого прямоугольника во второй.
//Можно ходить в любую сторону.
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <complex>
#include <iostream>
///////////////////////////////////////////////////////////////////////////////
typedef int                             T_coord;
typedef std::complex    < T_coord   >   T_cell;
///////////////////////////////////////////////////////////////////////////////
struct  T_rect
{
    //-------------------------------------------------------------------------
    char    name_symb_;
    T_cell  lower_left_;
    T_cell  top_right_;
    //-------------------------------------------------------------------------
    T_rect( char    name_symb )
        :
        name_symb_  ( name_symb )
    {}
    //-------------------------------------------------------------------------
    void    input()
    {
        std::cout   <<  "\nEnter cells of rectangle "
                    <<  name_symb_
                    <<  " in form (1,2)"
                    <<  std::endl;
 
        std::cout   <<  "\tlower left\t: ";
        std::cin    >>  lower_left_;
 
        std::cout   <<  "\ttop right_\t: ";
        std::cin    >>  top_right_;
    }
    //-------------------------------------------------------------------------
    int     king_dist_to( T_rect    const   &   r )
    {
        bool    this_left   =       lower_left_     .real()
                                <=  r.lower_left_   .real();
 
        bool    this_lower  =       lower_left_     .imag()
                                <=  r.lower_left_   .imag();
 
        auto    rect_left   =   *this;
        auto    rect_right  =   r;
 
        auto    rect_lower  =   *this;
        auto    rect_top    =   r;
 
        if( !this_left  )   { std::swap     ( rect_left,    rect_right  );  }
        if( !this_lower )   { std::swap     ( rect_lower,   rect_top    );  }
 
        auto    dist_horiz  =       rect_right  .lower_left_    .real()
                                -   rect_left   .top_right_     .real();
 
        auto    dist_vert   =       rect_top    .lower_left_    .imag()
                                -   rect_lower  .top_right_     .imag();
 
        dist_horiz          =   std::max( dist_horiz,   0 );
        dist_vert           =   std::max( dist_vert,    0 );
 
        return  std::max    (
                                dist_horiz,
                                dist_vert
                            );
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    T_rect  A('A');
    T_rect  B('B');
 
    A.input();
    B.input();
 
    std::cout   <<  A.king_dist_to(B)
                <<  std::endl;
}
1
Effsus
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 16
15.10.2016, 20:32  [ТС] #8
Цитата Сообщение от Новичок Посмотреть сообщение
Вот с этого и надо было начинать. Потому что найти путь за 0.1 секунду при таких ограничениях нереально, а длину можно. Но все равно какое-то странное условие. Можете примеры тестов привести(с объяснениями желательно)?
На картинке написано не на русском, но объясню. На Pascal/C/C++ один тест должен выполняться за менее чем 0.1 секунды. На Java за менее чем 0.3 секунды. В архиве запаковал все тесты, которые должна пройти программа.
Там где фото с числами:
8 и 9 - размеры поля
1 и 2 ; 4 и 4 - размеры первого прямоугольника
6 и 8 ; 8 и 8 - размеры второго прямоугольника
4 - минимальное кол-во ходов
Если прямоугольники налегают друг на друга, то кол-во ходов 0 в ответ.
На последней фотке 3 теста с данными, которые даются.
0
Миниатюры
Найти кратчайший путь шахматного короля   Найти кратчайший путь шахматного короля   Найти кратчайший путь шахматного короля  

Вложения
Тип файла: zip karalis.zip (35.0 Кб, 1 просмотров)
Nosey
1348 / 399 / 107
Регистрация: 22.10.2014
Сообщений: 861
Завершенные тесты: 2
15.10.2016, 20:43 #9
Mr.X, Вы вроде ищите расстояние между углами, а возможно еще и расстояние между сторонами. (один высокий прямоугольник, второй широкий, один находится над другим).
Пардоньте, если ошибаюсь

Effsus, Вот, общее "решение" на русском http://noregret.org/tutor/n/collision/#2
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
15.10.2016, 20:52 #10
Цитата Сообщение от Nosey Посмотреть сообщение
Mr.X, Вы вроде ищите расстояние между углами
Не, нахожу расстояния между прямоугольниками по горизонтали и вертикали и возвращаю максимальное из них.

Добавлено через 4 минуты
Цитата Сообщение от Nosey Посмотреть сообщение
Пардоньте, если ошибаюсь
Стопроцентно ошибаетесь! Работающую программу невозможно опровергнуть теоретическими выкладками, а только тестом, демонстрирующим ее неправильную работу!
1
Nosey
1348 / 399 / 107
Регистрация: 22.10.2014
Сообщений: 861
Завершенные тесты: 2
15.10.2016, 20:53 #11
Цитата Сообщение от Mr.X Посмотреть сообщение
Не, нахожу расстояния между прямоугольниками по горизонтали и вертикали и возвращаю максимальное из них.
Ах, да, посыпаю голову пеплом.
Effsus, Моё общее "решение" вам в пень не сдалось
0
Effsus
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 16
15.10.2016, 21:13  [ТС] #12
Цитата Сообщение от Mr.X Посмотреть сообщение
Не, нахожу расстояния между прямоугольниками по горизонтали и вертикали и возвращаю максимальное из них.
У меня почему-то много ошибок при компиляции.
0
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
15.10.2016, 21:29 #13
Цитата Сообщение от Effsus Посмотреть сообщение
У меня почему-то много ошибок при компиляции.
С++11 надо подключить.
0
Effsus
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 16
16.10.2016, 14:51  [ТС] #14
Цитата Сообщение от Mr.X Посмотреть сообщение
С++11 надо подключить.
К сожалению это не совсем то, что нужно.
Какие данные нужно ввести, чтобы получить минимальное кол-во ходов?
Вот вид поля:
0
Миниатюры
Найти кратчайший путь шахматного короля  
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
16.10.2016, 15:08 #15
Effsus, я так не играю, у вас доска перевернутая! Я писал из предположения, что у нас вертикальные коордитаны увеличиваются снизу вверх, как оно и есть на шахматной доске!
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.10.2016, 15:08
Привет! Вот еще темы с ответами:

Дан проходной лабиринт с одним входом и выходом. Найти кратчайший путь для прохождения этого лабиринта - C++
Дан проходной лабиринт с одним входом и выходом. Найти кратчайший путь для прохождения этого лабиринта.

Кратчайший путь в графе. - C++
Такая задача: Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший путь из вершины s в вершину t. ...

Графы кратчайший путь ! - C++
Помогите написать функцию для поиска кратчайшего пути между вершинами которые задаются с клавы я написал правда получилось что это...

Кратчайший путь коня с++ - C++
помогите пожалуйста написать алгоритм кротчайшего пути коня на шахматной доске из А в Б


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
16.10.2016, 15:08
Ответ Создать тему
Опции темы

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