Вопрос на основе кратчайшего наибольшего расстояния от источника до пункта назначения - PullRequest
Новая
       23

Вопрос на основе кратчайшего наибольшего расстояния от источника до пункта назначения

0 голосов
/ 03 апреля 2019

Компания хочет исследовать некоторые редкие элементы для своего производства полупроводников. Ученые используют одно транспортное средство, чтобы исследовать область, чтобы найти редкие элементы. Транспортное средство может двигаться только в исследуемом регионе, где дороги уже построены. Транспортное средство не может двигаться по неизведанному региону, где нет дорог. В нынешней ситуации редкие элементы присутствуют только в исследуемом регионе. Неисследованные области не содержат редких элементов. Площадь региона предоставлена ​​для разведки. Дороги обозначены цифрой 1, а там, где дороги отсутствуют, эта площадь обозначена цифрой 0. Редкие элементы будут только на тех дорогах, где уже изучены районы. Автомобиль может двигаться в четырех направлениях - вверх, вниз, влево и вправо. Кратчайший путь для транспортного средства к позиции редкого элемента называется Moving Path. Самый длинный из путей ко всем редким элементам из области под названием «Самое длинное расстояние». Ученым необходимо построить один исследовательский центр, чтобы исследовательский центр находился в том месте, где самый длинный путь к редким элементам будет самым коротким. Это называется самым коротким длинным расстоянием.

Например, красная, синяя и зеленая области представляют область редких элементов. (2, 2) представлен красным, (2, 8) представлен синим, а (7, 8) представлен зеленым. Итак, есть три редких элемента. Если исследовательский центр построен в точке (4, 4), то, скажем, расстояние до редкого элемента Red будет равно 4, расстояние до редкого элемента Blue будет равно 6, а расстояние до редкого элемента Green будет равно 7. Таким образом, наибольшее расстояние будет равно 7.

Теперь, используя тот же регион выше, если исследовательский центр построен в (4, 5), тогда расстояние до Редкого элемента Red будет 5, Расстояние до Редкого элемента Blue будет 5, а расстояние до Редкого элемента Green - 6. Так Наибольшее расстояние будет 6. Поэтому, когда исследовательский центр будет построен в точке (4, 5), самое длинное расстояние будет самым коротким. И значение Shortest Longest Distance будет равно 6. Это будет выход. Может быть несколько мест, откуда самое короткое самое длинное расстояние может быть одинаковым. Например, если исследовательский центр построен в (5, 5), то самое короткое самое длинное расстояние будет равно 6. Поэтому напишите программу, чтобы найти самое короткое расстояние.

Ограничения: • Предоставленная область будет квадратной областью, то есть NxN (где 5 <= N <= 20). </p>

• Может быть минимум 2 редких элемента и максимум 4 редких элемента, то есть 2 <= C <= 4. </p>

• Дороги обозначены цифрой 1, а дорожная зона не обозначена цифрой 0.

• Транспортное средство может двигаться только по дорогам в исследуемой области.

• Редкие элементы будут присутствовать только там, где есть дорога. Редкие элементы не будут присутствовать там, где нет дорог.

• Автомобиль может двигаться в направлениях ВВЕРХ, ВНИЗ, ВЛЕВО и ВПРАВО.

• Начальный индекс для редкого элемента считается равным 1.

Введите:

• В первой строке будет указано количество тестов. Вторая строка укажет область области (N) и количество редких элементов (C).

Следующие строки C будут содержать положение редких элементов.

После этого N строк предоставят информацию о регионе, где можно указать, где дороги присутствуют, а где нет.

Выход:

• Выведите #testcase, затем пробел и самое короткое самое длинное расстояние.

Пример ввода: 

5
5 2
4 3
3 4
1 1 0 0 0
1 1 0 0 0
1 1 1 1 1
1 1 1 0 1
1 1 1 1 1
8 2
5 6
6 4
1 1 1 1 1 1 0 0
1 1 1 1 1 1 1 0
1 1 0 1 0 1 1 0
1 1 1 1 0 1 1 0
1 1 1 1 1 1 1 0
1 1 1 1 1 1 1 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
10 3
8 2
5 3
7 1
0 0 0 1 1 1 1 1 1 0
1 1 1 1 1 1 1 1 1 0
1 0 0 1 0 0 0 0 1 0
1 1 1 1 1 1 1 1 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 0 0 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1
15 4
11 15
15 9
1 2
14 3
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 0 1 0 0 0 1 0 0 0 0 1 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
0 0 1 0 0 0 1 1 1 1 1 1 1 0 1
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
20 4
13 6
20 4
1 2
17 16
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 0 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1
1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0

Пример вывода: 

#1 1
#2 2
#3 2
#4 12
#5 15

Я пытался решить этот вопрос, используя метод возврата. Он дает мне правильный вывод для тестовых примеров № 1 и № 2, но он застревает в бесконечном цикле для остальных тестовых случаев. 

#include<iostream>

#include<fstream>

using namespace std;

int a[22][22];
int x[4];
int y[4];
bool visit[22][22];
int N;
int ele; //Number of rare elements

void unvisit()
{
    for(int i=0;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            visit[i][j]=false;
        }
    }
}

bool isSafe(int x, int y)
{
    if(x>=N || y>=N || x<0 || y<0 || a[x][y]==0 || visit[x][y]==true )
        return false;
    return true;
}
int min_distance(int x, int y,  int d_x, int d_y, int dis)
{
    //cout<<"x:"<<x<<" "<<"y:"<<y<<" "<<dis<<" "<<d_x<<" "<<d_y<<endl;
    int left=999,right=999,up=999,down=999;
    if(x==d_x && y==d_y)
    {
        //cout<<"MATCH:"<<dis<<endl;
        return dis;
    }
    //cout<<min_dis;
    visit[x][y]=true;


        if(isSafe(x,y+1))
            right=min_distance(x,y+1,d_x,d_y,dis+1);
        if(isSafe(x,y-1))
            left=min_distance(x,y-1,d_x,d_y,dis+1);
        if(isSafe(x+1,y))
            down=min_distance(x+1,y,d_x,d_y,dis+1);
        if(isSafe(x-1,y))
            up=min_distance(x-1,y,d_x,d_y,dis+1);

        visit[x][y]=false;

        return min(min(min(right,left),down),up);





}

int main()
{
    int d1=-999,d2=999;


    fstream myfile;

    myfile.open("Input.txt");



    myfile>>N>>ele;



    for(int i=0;i<ele;++i)
    {
        myfile>>x[i]>>y[i];
    }

    for(int i=0;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {
            myfile>>a[i][j];
        }
    }

    for(int i=0;i<N;++i)
    {
        for(int j=0;j<N;++j)
        {

            if(a[i][j]==1)
            {
                d1=-999;
            for(int k=0;k<ele;++k)
            {
                //cout<<i<<" "<<j<<" "<<endl;


                unvisit();
                d1=max(d1,min_distance(i,j,x[k],y[k],0));

                //cout<<"x:"<<i<<" "<<"y:"<<j<<" "<<"d1:"<<d1<<endl;;

            }
            }

        d2=min(d2,d1);
        //cout<<"d2:"<<d2<<endl;




        }
    }

    cout<<d2<<endl;

    myfile.close();

    return 0;




}

Может кто-нибудь сказать мне, почему мое решение не работает? Спасибо!

1 Ответ

0 голосов
/ 04 апреля 2019

Логика верна.В коде нет ошибок.Проблема в том, что для возврата требуется очень много времени.Это не очень подходит для решения задач минимального расстояния, когда матрицы плотные.BFS является оптимальным способом решения таких проблем.

...