-3

Company wants to explore some of the rare elements for its semiconductor manufacturing. Scientists use one vehicle to explore the region in order to find the rare elements. The vehicle can move only in explored region where roads have already been constructed. The vehicle cannot move on unexplored region where roads are not there. In the current situation, rare elements are present in explored region only. Unexplored regions do not contain any rare elements. Square region is provided for exploration. Roads are represented by 1 and where roads are not present that area is represented by 0. Rare elements will only be on the roads where regions have already been explored. Vehicle can move in four directions – up, down, left and right. The shortest path for vehicle to a rare element position is called Moving Path. The longest of the paths to all rare elements from a region called Longest Distance. Scientists need to construct one research center so that the research center will be at the position where the longest path to the rare elements will be shortest. This is called Shortest Longest Distance.

For example, Red, Blue and Green area represents Rare Element area. (2, 2) is represented as Red, (2, 8) is represented as Blue and (7, 8) is represented as Green. So there are three rare elements. If research center is constructed at (4, 4) then say distance to Red rare element will be 4, distance to Blue rare element will be 6 and distance to Green rare element will be 7. So the Longest distance will be 7.

Now using the same region above, if research center is constructed at (4, 5) then distance to Red rare element will be 5, distance to Blue rare element will be 5 and distance to Green rare element will be 6. So the Longest distance will be 6. So when research center is constructed at (4, 5) then the longest distance will be shortest. And the value of the Shortest Longest Distance will be 6. This will be the output. There can be multiple locations from where the shortest longest distance can be same. For example if research center is constructed at (5, 5) then still the Shortest Longest distance will be 6. So write a program to find the Shortest Longest Distance.

Constraints: • The region provided will be square region i.e. NxN (where 5 <= N <= 20).

• There can be minimum of 2 rare elements and maximum of 4 rare elements, i.e. 2 <= C <= 4.

• Roads are represented by 1 while no road area is represented by 0.

• Vehicle can move only on roads in explored area.

• The rare elements will only be present where road are there. Rare elements will not be present where roads are not present.

• Vehicle can move in UP, DOWN, LEFT and RIGHT directions.

• The starting index for rare element is considers as 1.

Input:

• First line will be the number of test cases. Second line will indicate region area (N) and number of rare elements (C).

Next C lines will contain the position of rare elements.

After that N lines will provide the region details where to tell where roads are present and where roads are not present.

Output:

• Output #testcase followed by space and then shortest longest distance.

Sample Input:

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

Sample Output:

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

I have tried solving this question using the backtracking approach. It is giving me correct output for testcase #1 and #2 but it gets stuck in an infinite loop for the rest of the test cases. 

#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;




}

Can someone tell me why my solution is not working? Thanks!

Christophe
  • 68,716
  • 7
  • 72
  • 138
Sank_BE
  • 33
  • 5
  • *it gets stuck in an infinite loop for the rest of the test cases* sounds like a perfect time to break out the debugger and walk through the loop a time or two to see why it got stuck. If this tells you what you need in order to solve the problem, awesome! If not, use what you've learned to conduct more experiments. – user4581301 Apr 03 '19 at 19:46
  • I have no clue why it is getting stuck. As you can see, I have tried printing outputs. Forget about the rest of the question. Say, we have to find the minimum distance from one point to another. That's what the function min_distance() is doing. Why is it getting stuck or where is it logically wrong? Thanks. – Sank_BE Apr 03 '19 at 19:55
  • [What I mean by a debugger](https://en.wikipedia.org/wiki/Debugger) – user4581301 Apr 03 '19 at 20:12
  • https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ https://stackoverflow.com/questions/2069367/how-to-debug-using-gdb – Yunnosch Apr 03 '19 at 20:27
  • Looks like program logic was correct. It was just taking awful lot of time. Looks like BFS using queue is the optimal way to solve the problem like this. – Sank_BE Apr 03 '19 at 23:36
  • I am answering my own question... – Sank_BE Apr 04 '19 at 03:49

2 Answers2

0

The logic is correct. There are no errors in the code. The problem is that the backtracking is taking awful lot of time. It is not very suitable to solve minimum distance problems when the matrices are dense. BFS is the optimal way to solve such problems.

Sank_BE
  • 33
  • 5
0

problem is that you do not check for (i,j) to all possible 4 rare points reach or not

ANKIT
  • 1