aboutsummaryrefslogtreecommitdiff
path: root/path_crossing.c
diff options
context:
space:
mode:
Diffstat (limited to 'path_crossing.c')
-rw-r--r--path_crossing.c71
1 files changed, 71 insertions, 0 deletions
diff --git a/path_crossing.c b/path_crossing.c
new file mode 100644
index 0000000..039556a
--- /dev/null
+++ b/path_crossing.c
@@ -0,0 +1,71 @@
+// 1496. Path Crossing
+#include "leetcode.h"
+
+/*
+ * 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 'true' if the path crosses itself at any point, that is, if at
+ * any time you are on a location you have previously visited. return 'false'
+ * otherwise.
+ */
+
+typedef struct {
+ uint val;
+ int r_type;
+ int c_type;
+} data;
+
+bool isPathCrossing(char *path) {
+ int n = strlen(path), m = 5 * n;
+ data **hash = calloc(m, sizeof(data *));
+ hash[0] = malloc(sizeof(data));
+ hash[0]->val = 0;
+ hash[0]->r_type = 1;
+ hash[0]->c_type = 1;
+ int r = 0, c = 0;
+ bool ans = 0;
+ for (int i = 0; i < n; i++) {
+ if (ans)
+ break;
+ switch (path[i]) {
+ case 'N':
+ r++;
+ break;
+ case 'S':
+ r--;
+ break;
+ case 'W':
+ c++;
+ break;
+ default:
+ c++;
+ }
+ uint val = abs(r) * 10000 + abs(c), d = val;
+ while (1) {
+ if (!hash[d % m]) {
+ hash[d % m] = malloc(sizeof(data));
+ hash[d % m]->val = val;
+ hash[d % m]->r_type = r >= 0;
+ hash[d % m]->c_type = c >= 0;
+ break;
+ } else if (hash[d % m]->val == val && hash[d % m]->r_type == r >= 0 &&
+ hash[d % m]->c_type == c >= 0) {
+ ans = 1;
+ break;
+ } else
+ d++;
+ }
+ }
+ for (int i = 0; i < m; i++)
+ if (hash[i])
+ free(hash[i]);
+ free(hash);
+ return ans;
+}
+
+int main() {
+ char *p1 = "NES", *p2 = "NESWW";
+ printf("%d\n", isPathCrossing(p1)); // expect: 0
+ printf("%d\n", isPathCrossing(p2)); // expect: 1
+}