shrishty
BAN USERThis is the recursive solution. Can easily be mapped to dynamic programming
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int minSteps(int M[5][5], int index, unordered_map<int, int> m, bool left)
{
cout<<"index = "<<index<<" isleft = "<<left<<endl;
if(index >= 5)
{
cout<<"Recursion ended"<<endl;
return 0;
}
int steps = 0;
if(m.find(index) != m.end())
{
if(left)
{
for(int j = 0; j < 5; j++)
{
steps++;
if(M[index][j] == 0)
{
m[index] -= 1;
if(m[index] == 0)
{
return min(5 + minSteps(M, index+1, m, false),
2 * steps - 1 + minSteps(M, index + 1, m, true));
}
}
}
}
else
{
for(int j = 4; j >=0; j--)
{
steps++;
if(M[index][j] == 0)
{
m[index] -= 1;
if(m[index] == 0)
{
return min(5 + minSteps(M, index + 1, m, true),
2 * steps - 1 + minSteps(M, index + 1, m, false));
}
}
}
}
}
else
{
if(left)
{
return min(5 + minSteps(M, index + 1, m, false),
0 + minSteps(M, index + 1, m, true));
}
else
{
return min(5 + minSteps(M, index + 1, m, true),
0 + minSteps(M, index + 1, m, false));
}
}
return 0;
}
int main()
{
vector<pair<int, int>> ls = { {1, 1}, {1, 4}, {2, 2}, {3, 4}};
int R, C;
R = 5; C = 5;
int M[5][5];
unordered_map<int,int> m;
for(int i = 0; i < R; i++)
{
for(int j = 0; j < C; j++)
{
M[i][j] = 1;
}
}
for(auto itr: ls)
{
M[itr.first][itr.second] = 0;
if(m.find(itr.first) == m.end())
{
m[itr.first] = 1;
}
else
{
m[itr.first] += 1;
}
}
cout<<minSteps(M, 0, m, true)<<endl;
return 0;
}
The code can be beautified. I have assumed matrix size is 5x5 but it can be easily generalized.
int[][] room = new int[][]{
{1,1,1,1,1},
{1,0,1,1,0},
{1,1,0,1,1},
{1,1,1,1,0},
{1,1,1,1,1}
};
this is the sequence of steps - (1, 0), (1, 1), (1, 2), (1,3),(1,4), (2,4), (2,3),(2,2),(2,3),(2,4),(3,4)
All computers are repaired at this point.
I dont think maps would work here.
- shrishty October 17, 2018Consider this example
p1 -> a, b, c
p2 -> d
p3 -> d, a
p4 -> e
in this case there is only one unique contact that is p1. This problem can be thought as a graph problem where we care supposed to find all disconnected graphs.
In above example p1, p2 and p3 are connected together hence same contact. p4 is disconnected.