Created
September 8, 2018 05:05
-
-
Save gunpreet34/b58c38b3556271059182244676ba06a1 to your computer and use it in GitHub Desktop.
Code for question: There is a source (S) and destination (D) and a spacecraft has to go from S to D. There are N number of wormholes in between which has following properties: Each wormhole has an entry and an exit. Each wormhole is bi-directional i.e. one can enter and exit from any of the ends. The time to cross the wormhole is given and the s…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
using namespace std; | |
#define i_max 2147483647 | |
int nw,sx,sy,dx,dy;//Source and destination co-ordinates | |
int dist[1001][1001]; | |
bool set[1001][1001]; | |
class Wormhole{ | |
public: | |
int x1,y1,x2,y2,cost; | |
void get(){ | |
cin >> x1 >> y1 >> x2 >> y2 >> cost; | |
} | |
}; | |
Wormhole A[10]; | |
int row_mov[] = {1,-1,0,0}; | |
int col_mov[] = {0,0,1,-1}; | |
void initializeArrays(int m,int n){ | |
//Filling array with 1s | |
for(int i=0;i<m;i++){ | |
for(int j=0;j<n;j++){ | |
dist[i][j] = i_max; | |
set[i][j] = false; | |
} | |
} | |
} | |
void setMinRowCol(int &row,int &col){ | |
int min_dist=i_max,min_i=-1,min_j=-1; | |
for(int i=1;i<=dx;i++){ | |
for(int j=1;j<=dy;j++){ | |
if(!set[i][j] && dist[i][j]<min_dist){ | |
min_dist = dist[i][j]; | |
min_i = i; | |
min_j = j; | |
} | |
} | |
} | |
row = min_i; | |
col = min_j; | |
} | |
int wormentry(int i,int j) | |
{ | |
for(int k=0;k<nw;k++) | |
{ | |
if(A[k].x1==i && A[k].y1==j) | |
return k; | |
} | |
return -1; | |
} | |
int wormexit(int i,int j) | |
{ | |
for(int k=0;k<nw;k++) | |
{ | |
if(A[k].x2==i && A[k].y2==j) | |
return k; | |
} | |
return -1; | |
} | |
bool isValid(int i,int j){ | |
if(i<1 || j<1 || i>dx || j>dy){ | |
return false; | |
} | |
return true; | |
} | |
int findMinCost(){ | |
initializeArrays(dx+1,dy+1); | |
//Run dijkstra | |
dist[sx][sy] = 0;//Distance from source to source is 0 | |
//set[sx][sy] = true;//We have reached source | |
for(int i=1;i<=dx*dy;i++){ | |
int row=-1,col=-1; | |
setMinRowCol(row,col);//Find min row,col that are unset and proceed with min_dist path | |
if(row == -1 && col == -1){//If not found then break | |
break; | |
} | |
if(row == dx && col == dy){//If we've reached destination, return the cost | |
return dist[row][col]; | |
} | |
set[row][col] = true;//Set the current row,col | |
for(int j=0;j<4;j++)//Move in all 4 directions | |
{ | |
int x = row + row_mov[j]; | |
int y = col + col_mov[j]; | |
if(isValid(x,y) && !set[x][y] && dist[x][y]>dist[row][col]+1) | |
dist[x][y] = dist[row][col] + 1; | |
} | |
int w_entry = wormentry(row,col);//If worm entry is at row,col ,i.e., row = x1 & col = y1 then exit is at x2,y2 | |
if(w_entry!=-1) | |
{ | |
int x = A[w_entry].x2; | |
int y = A[w_entry].y2; | |
if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_entry].cost) //If cost of wormhole is minimum go through the wormhole | |
dist[x][y] = dist[row][col]+A[w_entry].cost; | |
} | |
int w_exit = wormexit(row,col);//If worm exit is at row,col ,i.e., row = x2 & col = y2 then entry is at x1,y1 | |
if(w_exit!=-1) | |
{ | |
int x = A[w_exit].x1; | |
int y = A[w_exit].y1; | |
if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_exit].cost) //If cost of wormhole is minimum go through the wormhole | |
dist[x][y] = dist[row][col]+A[w_exit].cost; | |
} | |
} | |
return -1; | |
} | |
int main(){ | |
cin >> sx >> sy >> dx >> dy;//Scanning source and destination | |
cin >> nw;//No of wormholes | |
//Scanning wormholes info | |
for(int i=0;i<nw;i++){ | |
A[i].get(); | |
} | |
cout << findMinCost(); | |
return 0; | |
} |
if we return cost just after reaching the destination then there might be chance new future updated value is smaller
In this solution can you tell me how to take input for wormhole coordinates?? . Please let me know.
Please give one input and output example... Because in my case it always return - 1 as per your code.
Ill send you my whole code
…On Fri, Oct 11, 2019, 10:52 AM fuloriyaChetan ***@***.***> wrote:
In this solution can you tell me how to take input for wormhole
coordinates?? . Please let me know.
—
You are receiving this because you commented.
Reply to this email directly, view it on GitHub
<https://gist.github.com/b58c38b3556271059182244676ba06a1?email_source=notifications&email_token=AHKF2UJKNPIDFRGLG5M4Q2LQOAERXA5CNFSM4I6WJ5F2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2JSQ#gistcomment-3052328>,
or unsubscribe
<https://github.com/notifications/unsubscribe-auth/AHKF2UM7WLX2UZ3KAZM7RTDQOAERXANCNFSM4I6WJ5FQ>
.
#include<iostream>
using namespace std;
#define i_max 214748364
int nw,sx,sy,dx,dy;//Source and destination co-ordinates
int dist[1001][1001];
bool set[1001][1001];
class Wormhole{
public:
int x1,y1,x2,y2,cost;
void get(){
cin >> x1 >> y1 >> x2 >> y2 >> cost;
}
};
Wormhole A[10];
int row_mov[] = {-1,0,0,1};
int col_mov[] = {0,-1,1,0};
void initializeArrays(int m,int n){
//Filling array with 1s
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dist[i][j] = i_max;
set[i][j] = false;
}
}
}
void setMinRowCol(int &row,int &col){
int min_dist=i_max,min_i=-1,min_j=-1;
for(int i=0;i<=180;i++){
for(int j=0;j<=180;j++){
if(!set[i][j] && dist[i][j]<min_dist){
min_dist = dist[i][j];
min_i = i;
min_j = j;
}
}
}
row = min_i;
col = min_j;
}
int wormentry(int i,int j)
{
for(int k=0;k<nw;k++)
{
if(A[k].x1==i && A[k].y1==j)
return k;
}
return -1;
}
int wormexit(int i,int j)
{
for(int k=0;k<nw;k++)
{
if(A[k].x2==i && A[k].y2==j)
return k;
}
return -1;
}
bool isValid(int i,int j){
if(i<0 || j<0 || i>180 || j>180){
return false;
}
return true;
}
int findMinCost(){
initializeArrays(181,181);
//Run dijkstra
dist[sx][sy] = 0;//Distance from source to source is 0
//set[sx][sy] = true;//We have reached source
for(int i=1;i<=(181)*(181);i++){
//cout<<i;
int row=-1,col=-1;
setMinRowCol(row,col);//Find min row,col that are unset and proceed with
min_dist path
if(row == -1 && col == -1){//If not found then break
break;
}
set[row][col] = true;//Set the current row,col
for(int j=0;j<4;j++)//Move in all 4 directions
{
int x = row + row_mov[j];
int y = col + col_mov[j];
if(isValid(x,y) && !set[x][y] && dist[x][y]>dist[row][col]+1)
{ dist[x][y] = dist[row][col] + 1;
// if(x>90)cout<<dist[x][y]<<" "<<x<<y<<" ";
}
}
int w_entry = wormentry(row,col);//If worm entry is at row,col
,i.e., row = x1 & col = y1 then exit is at x2,y2
if(w_entry!=-1)
{
int x = A[w_entry].x2;
int y = A[w_entry].y2;
if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_entry].cost)
//If cost of wormhole is minimum go through the wormhole
dist[x][y] = dist[row][col]+A[w_entry].cost;
}
int w_exit = wormexit(row,col);//If worm exit is at row,col ,i.e.,
row = x2 & col = y2 then entry is at x1,y1
if(w_exit!=-1)
{
int x = A[w_exit].x1;
int y = A[w_exit].y1;
if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_exit].cost) //If
cost of wormhole is minimum go through the wormhole
dist[x][y] = dist[row][col]+A[w_exit].cost;
}
}
//If we've reached destination, return the cost
return dist[dx][dy];
}
int main(){
cin >> sx >> sy >> dx >> dy;//Scanning source and destination
cin >> nw;//No of wormholes
//Scanning wormholes info
for(int i=0;i<nw;i++){
A[i].get();
}
cout << findMinCost();
return 0;
}.
I used 181*181 because in my case there is a exit of warm hole at 120,180
so you have to take the maximum coordinate of input let say x,y then it
will be 1to x+1*y+1 please take care of that .
…On Fri, Oct 11, 2019, 5:15 PM AASHI BHATIA ***@***.***> wrote:
Ill send you my whole code
On Fri, Oct 11, 2019, 10:52 AM fuloriyaChetan ***@***.***>
wrote:
> In this solution can you tell me how to take input for wormhole
> coordinates?? . Please let me know.
>
> —
> You are receiving this because you commented.
> Reply to this email directly, view it on GitHub
> <https://gist.github.com/b58c38b3556271059182244676ba06a1?email_source=notifications&email_token=AHKF2UJKNPIDFRGLG5M4Q2LQOAERXA5CNFSM4I6WJ5F2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2JSQ#gistcomment-3052328>,
> or unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AHKF2UM7WLX2UZ3KAZM7RTDQOAERXANCNFSM4I6WJ5FQ>
> .
>
Your code was absolutely fine it just that in for loop you have to start
from zero because your array index can zero for source
…On Fri, Oct 11, 2019, 5:20 PM AASHI BHATIA ***@***.***> wrote:
#include<iostream>
using namespace std;
#define i_max 214748364
int nw,sx,sy,dx,dy;//Source and destination co-ordinates
int dist[1001][1001];
bool set[1001][1001];
class Wormhole{
public:
int x1,y1,x2,y2,cost;
void get(){
cin >> x1 >> y1 >> x2 >> y2 >> cost;
}
};
Wormhole A[10];
int row_mov[] = {-1,0,0,1};
int col_mov[] = {0,-1,1,0};
void initializeArrays(int m,int n){
//Filling array with 1s
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
dist[i][j] = i_max;
set[i][j] = false;
}
}
}
void setMinRowCol(int &row,int &col){
int min_dist=i_max,min_i=-1,min_j=-1;
for(int i=0;i<=180;i++){
for(int j=0;j<=180;j++){
if(!set[i][j] && dist[i][j]<min_dist){
min_dist = dist[i][j];
min_i = i;
min_j = j;
}
}
}
row = min_i;
col = min_j;
}
int wormentry(int i,int j)
{
for(int k=0;k<nw;k++)
{
if(A[k].x1==i && A[k].y1==j)
return k;
}
return -1;
}
int wormexit(int i,int j)
{
for(int k=0;k<nw;k++)
{
if(A[k].x2==i && A[k].y2==j)
return k;
}
return -1;
}
bool isValid(int i,int j){
if(i<0 || j<0 || i>180 || j>180){
return false;
}
return true;
}
int findMinCost(){
initializeArrays(181,181);
//Run dijkstra
dist[sx][sy] = 0;//Distance from source to source is 0
//set[sx][sy] = true;//We have reached source
for(int i=1;i<=(181)*(181);i++){
//cout<<i;
int row=-1,col=-1;
setMinRowCol(row,col);//Find min row,col that are unset and proceed with
min_dist path
if(row == -1 && col == -1){//If not found then break
break;
}
set[row][col] = true;//Set the current row,col
for(int j=0;j<4;j++)//Move in all 4 directions
{
int x = row + row_mov[j];
int y = col + col_mov[j];
if(isValid(x,y) && !set[x][y] && dist[x][y]>dist[row][col]+1)
{ dist[x][y] = dist[row][col] + 1;
// if(x>90)cout<<dist[x][y]<<" "<<x<<y<<" ";
}
}
int w_entry = wormentry(row,col);//If worm entry is at row,col
,i.e., row = x1 & col = y1 then exit is at x2,y2
if(w_entry!=-1)
{
int x = A[w_entry].x2;
int y = A[w_entry].y2;
if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_entry].cost)
//If cost of wormhole is minimum go through the wormhole
dist[x][y] = dist[row][col]+A[w_entry].cost;
}
int w_exit = wormexit(row,col);//If worm exit is at row,col ,i.e.,
row = x2 & col = y2 then entry is at x1,y1
if(w_exit!=-1)
{
int x = A[w_exit].x1;
int y = A[w_exit].y1;
if(!set[x][y] && dist[x][y]>dist[row][col]+A[w_exit].cost)
//If cost of wormhole is minimum go through the wormhole
dist[x][y] = dist[row][col]+A[w_exit].cost;
}
}
//If we've reached destination, return the cost
return dist[dx][dy];
}
int main(){
cin >> sx >> sy >> dx >> dy;//Scanning source and destination
cin >> nw;//No of wormholes
//Scanning wormholes info
for(int i=0;i<nw;i++){
A[i].get();
}
cout << findMinCost();
return 0;
}.
I used 181*181 because in my case there is a exit of warm hole at 120,180
so you have to take the maximum coordinate of input let say x,y then it
will be 1to x+1*y+1 please take care of that .
On Fri, Oct 11, 2019, 5:15 PM AASHI BHATIA ***@***.***> wrote:
> Ill send you my whole code
>
> On Fri, Oct 11, 2019, 10:52 AM fuloriyaChetan ***@***.***>
> wrote:
>
>> In this solution can you tell me how to take input for wormhole
>> coordinates?? . Please let me know.
>>
>> —
>> You are receiving this because you commented.
>> Reply to this email directly, view it on GitHub
>> <https://gist.github.com/b58c38b3556271059182244676ba06a1?email_source=notifications&email_token=AHKF2UJKNPIDFRGLG5M4Q2LQOAERXA5CNFSM4I6WJ5F2YY3PNVWWK3TUL52HS4DFVNDWS43UINXW23LFNZ2KUY3PNVWWK3TUL5UWJTQAF2JSQ#gistcomment-3052328>,
>> or unsubscribe
>> <https://github.com/notifications/unsubscribe-auth/AHKF2UM7WLX2UZ3KAZM7RTDQOAERXANCNFSM4I6WJ5FQ>
>> .
>>
>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
can you give sample i/p and o/p ?