Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 05.01.2020, 13:15   #1
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию Помогите написать Input и Output для алгоритма

Вот Алгоритм:
Код:
#include "pch.h"
#include <iostream>
#include <set>
#include <queue>
#include <climits>
using namespace std;
 
static const int N = INT_MAX / 2;
 
// все 8 возможных движений
// для шахматного коня
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
 
// Проверяем, верны ли (x, y) координаты шахматной доски
bool valid(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= N)
        return false;
 
    return true;
}
 
// алгоритм BFS
struct Node
{
    // (x, y) координаты шахматной доски
    // dist - минимальное расстояние из предварительной точки к финальной
    int x, y, dist;
 
    // Node конструктор
    Node(int x, int y, int dist = 0) : x(x), y(y), dist(dist) {}
 
     
    // оператор перегрузки < operator
    bool operator<(const Node& o) const
    {
        return x < o.x || (x == o.x && y < o.y);
    }
};
 
// Находим минимальное количество шагов, предпринятых конем
// из предварительной точки к финальной, используем BFS
int BFS(Node src, Node dest)
{
    // проверяем была ли посещена ячейка матрицы или нет
    set<Node> visited;
 
    // создаем очередь и ставим в очередь первый узел
    queue<Node> q;
    q.push(src);
 
    // запустить до тех пор, пока очередь не станет пустой
    while (!q.empty())
    {
        // извлекаем передний узел из очереди и обрабатываем его
        Node node = q.front();
        q.pop();
 
        int x = node.x;
        int y = node.y;
        int dist = node.dist;
 
        // если пункт назначения достигнут, вернуть dist
        if (x == dest.x && y == dest.y)
            return dist;
 
        // пропускаем, если местоположение посещалось раньше
        if (!visited.count(node))
        {
            // пометим текущий узел как посещенный
            visited.insert(node);
 
            // проверяем все 8 возможных движений коня
            // и ставим каждое правильное движение в очередь
            for (int i = 0; i < 8; ++i)
            {
                // Получить новую действительную позицию коня из текущей
                // позиция на шахматной доске и поставить ее в очередь,
                // очередь с расстоянием +1
                int x1 = x + row[i];
                int y1 = y + col[i];
 
                if (valid(x1, y1))
                    q.push({ x1, y1, dist + 1 });
            }
        }
    }
 
    // вернуть бесконечность, если путь не возможен
    return INT_MAX;
}
 
 
int main()
{
    // исходные координаты
    Node src = { 0, 1 };
 
    // координаты пункта назначения
    Node dest = { 1, 1 };
 
    cout << "Минимальное количество шагов :" << BFS(src, dest);
 
    return 0;
}

Вот что должно быть в Input и Output

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

Вот как должно выглядеть:
2 - количество примеров
1 - количество шахматных коней
5 5 - начальная точка
5 6 - финальная точка
2 - количество шахматных коней
0 0 - начальная точка первого коня
1 0 - начальная точка второго коня
0 1 - финальная точка первого коня
1 1 - финальная точка второго коня

Ответ:
3 - ответ для первого коня
4 - ответ для второго коня


Вот как выглядит Input и Output в примере к заданию


ПОМОГИТЕ ПОЖАЛУЙСТА СДЕЛАТЬ, БУДУ ОЧЕЕНЬ БЛАГОДАРЕН!!!
Изображения
Тип файла: jpg 1.jpg (16.1 Кб, 20 просмотров)
Тип файла: jpg 2.jpg (8.5 Кб, 20 просмотров)
Programist_r вне форума Ответить с цитированием
Старый 09.01.2020, 19:53   #2
Programist_r
Пользователь
 
Регистрация: 08.05.2019
Сообщений: 27
По умолчанию

Код:
int main()
{


	int number_of_examples;
	int number_of_horse;
	int x, y;
	int a, b;

	Node src = { x,y };
	Node dest = { a,b };
	

	cin >> number_of_examples;                             //Число примеров

	for (int i = 1; i <= number_of_examples; i++)
	{
		cin >> number_of_horse;                         //Число коней

		for (int i = 1; i <= number_of_horse; i++)
		{
			cin >> x >> y;                            //Вписываем исходные координаты
		    
		}

		for (int i = 1; i <= number_of_horse; i++)
		{
			cin >> a >> b;                            //Вписываем координаты пункта назначения
			
		}

		cout << "Минимальное количество шагов :" << BFS(src, dest);

	}







	//// исходные координаты
	//Node src = { 0, 1 };

	//// координаты пункта назначения
	//Node dest = { 1, 1 };

	//cout << "Минимальное количество шагов :" << BFS(src, dest);

	return 0;
}
должно получиться примерно такое, но у меня оно не правильно работает
Можете помочь с Node, что бы оно правильно записывалось
Programist_r вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
где должны лежать input.txt и output.txt? Ципихович Эндрю Python 12 12.01.2018 09:22
Файлы output и input mazanakee Помощь студентам 0 22.02.2015 12:59
input,output Ainash Паскаль, Turbo Pascal, PascalABC.NET 8 04.11.2011 13:56
назначение Input и Output в Pascal sendruck Паскаль, Turbo Pascal, PascalABC.NET 5 18.07.2011 15:03
Длинны векторов, input output everliving Общие вопросы C/C++ 0 26.12.2010 20:05