问题基于从源到目的地的最短距离

问题描述 投票：-3回答：1

公司希望探索其半导体制造的一些稀有元素。科学家使用一种载体探索该地区，以寻找稀有元素。车辆只能在已建成道路的已探索区域内移动。车辆不能在没有道路的未开发区域移动。在目前的情况下，稀有元素仅存在于探索区域。未探测区域不包含任何稀有元素。广场区域用于勘探。道路以1表示，如果道路不存在，则该区域由0表示。稀有元素仅在已经探索过区域的道路上。车辆可以向上，向下，向左和向右四个方向移动。车辆到稀有元素位置的最短路径称为移动路径。距离称为最长距离的区域中所有稀有元素的最长路径。科学家需要建立一个研究中心，以便研究中心处于最短途径的稀有元素最短的位置。这称为最短最长距离。

例如，红色，蓝色和绿色区域代表稀有元素区域。 （2,2）表示为红色，（2,8）表示为蓝色，（7,8）表示为绿色。所以有三种稀有元素。如果研究中心建在（4,4）那么说距离红色稀有元素将是4，距蓝色稀有元素的距离将是6，与绿色稀有元素的距离将是7.因此最长距离将为7。

现在使用上面相同的区域，如果研究中心是在（4,5）建造的那么距离红色稀有元素将是5，距蓝色稀有元素的距离将是5，距离绿色稀有元素的距离将是6.所以最长距离因此当研究中心建在（4,5）时，最长的距离将是最短的。并且最短最长距离的值将为6.这将是输出。可以存在多个位置，其中最短的最长距离可以相同。例如，如果研究中心是在（5,5）建造的，那么最短最长距离仍然是6.所以写一个程序来找到最短最长距离。

约束条件：•所提供的区域将是方形区域，即NxN（其中5 <= N <= 20）。

•最少有2种稀有元素和最多4种稀有元素，即2 <= C <= 4。

•道路用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;




}

有人能告诉我为什么我的解决方案不起作用吗？谢谢！

c++ graph path-finding
1个回答
0
投票

逻辑是正确的。代码中没有错误。问题是回溯花费了大量的时间。当矩阵密集时，它不适合解决最小距离问题。 BFS是解决此类问题的最佳方式。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.