KROSS - Editorial

editorial
1

PROBLEM LINK:

Contest

Author: Sumukh Bhardwaj
Tester: Rahul Sharma
Editorialist: Sumukh Bhardwaj

DIFFICULTY:

EASY

PREREQUISITES:

Basic Programming

PROBLEM:

Given a string path, where path[i] = 'N', 'S', 'E' or 'W', each representing moving one unit north, south, east, or west, respectively. You start at the origin (0, 0) on a 2D plane and walk on the path specified by path.

Return 1 if the path crosses itself at any point, that is, if at any time you are on a location you have previously visited. Return 0 otherwise.

QUICK EXPLANATION:

Simulate the process and keep a note of all the visited cells, if reached a cell that is already visited return 1.

EXPLANATION:

To mark the visited cells, we can use an unordered map, we can either use a 2D map for x and y coordinates of cell or use a map from string to integer, here we first convert the x and y coordinate into strings. In this solution, we will be using the 2nd method.

We will traverse over the string and insert the cell into the map before inserting we will check if it already exists or not if it is then we return 1. If the string is finished we can return 0.

COMPLEXITIES

Here N is the size of string.

TIme Complexity: O(N).
All unordered map operations are O(1)

Space Complexity: O(N).
Space for unordered map.

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

unordered_map<string,int>mark;

bool isPathCrossing(string path) 
{
mark.clear();
int i,x=0,y=0,flag=0,n = path.length();
string key;

key=to_string(x)+"&"+to_string(y);
mark[key]=1;

for(i=0;i<n;i++)
{
	if(path[i]=='N')
		y++;
	else if(path[i]=='S')
		y--;
	else if(path[i]=='E')
		x++;
	else
		x--;
	
	key=to_string(x)+"&"+to_string(y);
  
	if(mark[key]==1)
		flag=1;
	
	mark[key]=1;
}

return flag;
}

int main() {
ios_base::sync_with_stdio(false);

long long t;

cin>>t;
while(t--)
{
	string k;
	cin>>k;
	cout<<isPathCrossing(k)<<endl;
}

return 0;
}
1 Like