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

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

Восстановить пароль Регистрация
 
Effsus
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 13
15.10.2016, 18:27     Найти кратчайший путь шахматного короля #1
Здравствуйте, имеется задача:
Есть шахматное поле NxM
N, M ≤ 10^9
На шахматном поле отмечено два прямоугольника размерами не менее 1х1.
Нужно найти кратчайший путь короля из первого прямоугольника во второй.
Можно ходить в любую сторону.
Каким алгоритмом лучше всего это будет реализовать?

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

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

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

Добавлено через 7 минут
Решаю задачи для получения опыта. Но с этой задачкой возникли трудности
Новичок
Модератор
 Аватар для Новичок
1141 / 712 / 148
Регистрация: 17.07.2012
Сообщений: 4,044
Записей в блоге: 1
Завершенные тесты: 2
15.10.2016, 20:16     Найти кратчайший путь шахматного короля #6
Цитата Сообщение от Effsus Посмотреть сообщение
Нужно вычислить минимальное кол-во ходов, нужное, чтобы король добрался из одного прямоугольника во второй.
Вот с этого и надо было начинать. Потому что найти путь за 0.1 секунду при таких ограничениях нереально, а длину можно. Но все равно какое-то странное условие. Можете примеры тестов привести(с объяснениями желательно)?
Цитата Сообщение от Effsus Посмотреть сообщение
Нужно найти кратчайший путь короля из первого прямоугольника во второй.
Зависит же еще от того где король стоит.
Mr.X
Эксперт С++
 Аватар для Mr.X
2803 / 1579 / 247
Регистрация: 03.05.2010
Сообщений: 3,673
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;
}
Effsus
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 13
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 теста с данными, которые даются.
Миниатюры
Найти кратчайший путь шахматного короля   Найти кратчайший путь шахматного короля   Найти кратчайший путь шахматного короля  

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

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

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

Как найти кратчайший путь в лабиринте? C++
C++ Как найти НЕ Кратчайший путь в графе ?
C++ С помощью метода волны найти кратчайший путь из одной клетки в другую (ход конём)

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

Или воспользуйтесь поиском по форуму:
Effsus
0 / 0 / 0
Регистрация: 05.11.2014
Сообщений: 13
16.10.2016, 15:12  [ТС]     Найти кратчайший путь шахматного короля #16
Цитата Сообщение от Mr.X Посмотреть сообщение
Effsus, я так не играю, у вас доска перевернутая! Я писал из предположения, что у нас вертикальные коордитаны увеличиваются снизу вверх, как оно и есть на шахматной доске!
Да, нужно было показать поле раньше Попробую решить задачу, переписав немного ваш код.
Yandex
Объявления
16.10.2016, 15:12     Найти кратчайший путь шахматного короля
Ответ Создать тему
Опции темы

Текущее время: 10:46. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru