Given a string str and four integers X1, Y1, X2 and Y2, where (X1, Y1) denotes the source coordinates and (X2, Y2) denotes the coordinates of the destination. Given a string str, the task is to find the minimum number of steps of the following four types required to reach destination from the source:
If str[i] = ‘E’: Convert (X1, Y1) to (X1 + 1, Y1).
If str[i] = ‘W’: Convert (X1, Y1) to (X1 – 1, Y1).
If str[i] = ‘N’: Convert (X1, Y1) to (X1, Y1 + 1).
If str[i] = ‘S’: Convert (X1, Ysub>1) to (X1, Y1 – 1).
If the destination cannot be reached, print -1.
Note: It is not necessary to use str[i] always and can be skipped. But skipped characters will add to the steps used.
Examples
Input: str = “SESNW”, x1 = 0, y1 = 0, x2 = 1, y2 = 1
Output: 4
Explanation:
To move from (0, 0) to (1, 1), it requires one ‘E’ and one ‘N’.
Therefore, the path defined by the substring “SESN” ensures that the destination is reached {(0, 0) -> skip S -> E(1, 0) -> skip S -> (1, 1)}.
Therefore, the minimum length of the string traversed is 4.
Input: str = “NNNNNNNN”, x1 = 1, y1 = 1, x2 = 1, y2 = 2
Output: 1
Explanation:
From current position (1, 1) it can move to co-ordinate (1, 2) using first ‘N’ direction.
Therefore, the minimum length of the string traverse is 1.
Approach: The idea is to iterate through the string and perform the moves until the destination is reached. Below are the steps:
Initialize four variable pos1, pos2, pos3 and pos4 to store the positions of E, W, N, S respectively.
Now, check if (x1, y1) is equal to (x2, y2) then the current position is already the destination so print 0.
Otherwise, iterate over the string and check the following four conditions:
If x2 > x1 then iterate until a ‘E’ comes and update that index in pos1.
If x2 < x1 then iterate until a ‘W’ comes and update that index in pos2.
If y2 > y1 then iterate until a ‘N’ comes and update that index in pos3.
If y2 < y1 then iterate until a ‘S’ comes and update that index in pos4.
After performing above operations check if x1 != x2 and y1 != y2 then print “-1” that means it is impossible to reach the destination.
Otherwise, find the max of pos1, pos2, pos3 and pos4 and print it.
Below is the implementation of the above approach:
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum length
// of string required to reach from
// source to destination
void minimum_length(int x1, int y1,
int x2, int y2,
string str)
{
// Size of the string
int n = str.size();
// Stores the index of the four
// directions E, W, N, S
int pos1, pos2, pos3, pos4;
pos1 = -1;
pos2 = -1;
pos3 = -1;
pos4 = -1;
// If destination reached
if (x1 == x2 && y1 == y2) {
cout << 0 << endl;
}
// Iterate over the string
else {
for (int i = 0; i < n; i++) {
// Move east
if (x2 > x1) {
// Change x1 according
// to direction E
if (str[i] == 'E') {
x1 = x1 + 1;
if (x1 == x2) {
pos1 = i;
}
}
}
// Move west
if (x2 < x1) {
// Change x1 according
// to direction W
if (str[i] == 'W') {
x1 = x1 - 1;
if (x1 == x2) {
pos2 = i;
}
}
}
// Move north
if (y2 > y1) {
// Change y1 according
// to direction N
if (str[i] == 'N') {
y1 = y1 + 1;
if (y1 == y2) {
pos3 = i;
}
}
}
// Move south
if (y2 < y1) {
// Change y1 according
// to direction S
if (str[i] == 'S') {
y1 = y1 - 1;
if (y1 == y2) {
pos4 = i;
}
}
}
}
int z;
// Store the max of all positions
z = max(max(max(pos1, pos2),
pos3),
pos4);
// Print the minimum length of
// string required
if (x1 == x2 && y1 == y2) {
cout << z + 1 << endl;
}
// Otherwise, it is impossible
else {
cout << "-1" << endl;
}
}
}
// Driver Code
int main()
{
// Given string
string str = "SESNW";
// Given source and destination
int x1 = 0, x2 = 1, y1 = 0, y2 = 1;
// Function Call
minimum_length(x1, y1, x2, y2, str);
return 0;
}
Output:
4
Time Complexity: O(N)
Auxiliary Space: O(1)
No comments:
Post a Comment