公司希望探索其半导体制造中的一些稀有元素。科学家使用一辆车探索该地区，以找到稀有元素。车辆只能在已经修建道路的探索区域移动。车辆不能在没有道路的未开发区域行驶。 在目前情况下，稀有元素仅存在于探索区域。未开发的地区不包含任何稀有元素。 提供方形区域供探索。道路由 1 表示，不存在道路时，该区域由 0 表示。稀有元素只会出现在已经探索过的道路上。车辆可以向四个方向移动 - 向上，向下，向左和向右移动。 车辆到稀有元素位置的最短路径称为移动路径。从称为最长距离的区域通向所有稀有元素的最长路径。 科学家需要建造一个研究中心，使研究中心处于通往稀有元素的最长路径最短的位置。这称为最短最长距离。
例如，红色、蓝色和绿色区域表示稀有元素区域。(2， 2) 表示为红色，(2， 8) 表示为蓝色，(7， 8) 表示为绿色。所以有三种罕见的元素。 如果研究中心建在(4,4)，那么说到红色稀有元素的距离将是4，到蓝色稀有元素的距离将是6，到绿色稀有元素的距离将是7。所以最长的距离将是 7。
现在使用上述相同区域，如果研究中心建在(4,5)，那么到红色稀有元素的距离将是5，到蓝色稀有元素的距离将是5，到绿色稀有元素的距离将是6。所以最长距离将是 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;
}
有人可以告诉我为什么我的解决方案不起作用吗？谢谢！
逻辑是正确的。代码中没有错误。问题是回溯需要花费大量时间。当矩阵密集时，不太适合解决最小距离问题。BFS是解决此类问题的最佳方法。
问题是您没有检查 (i，j) 到所有可能的 4 个稀有点是否达到