HackerRank Count Luck problem solution

In this HackerRank Count Luck problem solution we have given a forest as an N x M grid. and each empty cell is represented by . and blocked is represent by x. we can move LEFT, RIGHT, UP, and DOWN through empty cells but we cannot travel through a tree cell. the starting point is marked with the character M and the portkey is marked with a * asterisk sign and the upper left corner is indexed as (0,0). we have to find a way from starting cell to portkey and find out the maximum number of turns that we need to wave and we were also given the number of guesses waves for finding the portkey. so if the guess number and our count number are correct then we need to print Impressed and if not then print Oops!.

Problem solution in Python.

def search(g, m, n, i, j, c = 0):
    if g[i][j] == '*':
        return c
    g[i][j] = 0
    moves = getmoves(g, m, n, i, j)
    if len(moves) > 1:
        c += 1
    for mv in moves:
        res = search(g, m, n, mv[0], mv[1], c)
        if res != None:
            return res
    return None

def getmoves(g, m, n, i, j):
    l, v = [], ('.', '*')
    if i > 0 and g[i - 1][j] in v:
        l.append((i - 1, j))
    if j > 0 and g[i][j - 1] in v:
        l.append((i, j - 1))
    if i < m - 1 and g[i + 1][j] in v:
        l.append((i + 1, j))
    if j < n - 1 and g[i][j + 1] in v:
        l.append((i, j + 1))
    return l

for _ in range(int(input())):
    m, n = map(int, input().split())
    g = [list(input()) for _ in range(m)]
    k = int(input())
    for i in range(m):
        for j in range(n):
            if g[i][j] == 'M':
                print('Impressed' if search(g, m, n, i, j) == k else 'Oops!')
                break
    

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int test = 0; test < t; test++) {
            int n = in.nextInt();
            int m = in.nextInt();
            in.nextLine();
            char[][] matrix = new char[n][m];
            Queue<Pair> queue = new LinkedList<>();
            for (int i = 0; i < n; i++) {
                String line = in.nextLine();
                matrix[i] = line.toCharArray();
                for (int j = 0; j < m; j++) {
                    if (matrix[i][j] == 'M') {
                        queue.add(new Pair(i, j));
                        break;
                    }
                }
            }
            int k = in.nextInt();

            Map<Pair, Integer> map = new HashMap<>();
            map.put(queue.peek(), 0);

            Queue<Pair> newQueue = new LinkedList<>();
            while (!queue.isEmpty() && k >= 0) {
                Pair pair = queue.remove();
                int x = pair.x;
                int y = pair.y;

                int wandWaves = map.remove(pair);
                if (matrix[x][y] == '*') {
                    k -= wandWaves;
                    break;
                }

                if (needsWand(x, y, matrix)) wandWaves++;
                matrix[x][y] = 'X';

                pushToQueueAndPutToMap(new Pair[] {
                    new Pair(x, y - 1),
                    new Pair(x + 1, y),
                    new Pair(x, y + 1),
                    new Pair(x - 1, y)
                }, matrix, newQueue, wandWaves, map);

                if (queue.isEmpty()) {
                    queue = newQueue;
                    newQueue = new LinkedList<>();
                }
            }

            if (k == 0) {
                System.out.println("Impressed");
            } else {
                System.out.println("Oops!");
            }
        }
    }

    private static boolean needsWand(int x, int y, char[][] matrix) {
        int count = 0;
        if (isPath(x, y - 1, matrix)) count++;
        if (isPath(x + 1, y, matrix)) count++;
        if (isPath(x, y + 1, matrix)) count++;
        if (isPath(x - 1, y, matrix)) count++;
        return count > 1;
    }

    private static boolean isPath(int x, int y, char[][] matrix) {
        if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length) {
            return matrix[x][y] != 'X';
        }
        return false;
    }

    private static void pushToQueueAndPutToMap(Pair[] pairs, char[][] matrix, Queue<Pair> queue, int wandWaves, Map<Pair, Integer> map) {
        for (Pair pair : pairs) {
            int x = pair.x;
            int y = pair.y;
            if (x >= 0 && x < matrix.length && y >= 0 && y < matrix[0].length) {
                if (matrix[x][y] != 'X') {
                    queue.add(pair);
                    map.put(pair, wandWaves);
                }
            }
        }
    }

    private static class Pair {
        public int x;
        public int y;
        public Pair (int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int hashCode() {
            int hashCode = 1;
            hashCode = 31 * hashCode + x;
            hashCode = 31 * hashCode + y;
            return hashCode;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj == null) {
                return false;
            }
            if (!obj.getClass().equals(this.getClass())) {
                return false;
            }
            return x == ((Pair) obj).x && y == ((Pair) obj).y;
        }
    }
}

Problem solution in C++.

#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <string>
#include <cstring>

using namespace std;

typedef long long ll;

#define LEFT 0
#define UP 1
#define RIGHT 2
#define DOWN 3

int hantai(int dir) {
  if (dir == LEFT) return RIGHT;
  if (dir == UP) return DOWN;
  if (dir == RIGHT) return LEFT;
  if (dir == DOWN) return UP;
  return -1;
}

int main() {
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    int n, m;
    cin >> n >> m;
    string mMap[n];
    for (int j = 0; j < n; j++) cin >> mMap[j];
    int kk;
    cin >> kk;
    int sx, sy;
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < m; k++) {
        if (mMap[j][k] == 'M') {
          sx = k;
          sy = j;
          break;
        }
      }
    }
    // for (int j = 0; j < n; j++) {
    //   for (int k = 0; k < m; k++) {
    //     cout << char(mMap[j][k]);
    //   }
    //   cout << endl;
    // }
    // cout << endl;
    int memo[n][m];
    memset(memo, 0, sizeof(memo));
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, -1, 0, 1};
    stack <int> st; // x y val dir
    int cnt = 0;
    for (int j = 0; j < 4; j++) {
      int nx = sx+dx[j];
      int ny = sy+dy[j];
      if (nx >= 0 && ny >= 0 && nx < m && ny < n && mMap[ny][nx] == '.') cnt++;
    }
    for (int j = 0; j < 4; j++) {
      int nx = sx+dx[j];
      int ny = sy+dy[j];
      if (nx >= 0 && ny >= 0 && nx < m && ny < n && mMap[ny][nx] == '.') {
        st.push(sx);
        st.push(sy);
        if (cnt >= 2) {
          st.push(1);
        }else {
          st.push(0);
        }
        st.push(j);
      }
    }

    int ans = 0;
    bool goal = false;
    while (!st.empty() && !goal) {
      int dir = st.top(); st.pop();
      int val = st.top(); st.pop();
      int py = st.top(); st.pop();
      int px = st.top(); st.pop();

      int nx = px;
      int ny = py;
      while (true) {
        nx += dx[dir];
        ny += dy[dir];
        if (nx >= 0 && ny >= 0 && nx < m && ny < n && mMap[ny][nx] == '*') {
          goal = true;
          ans = val;
        }

        if (nx < 0 || ny < 0 || nx >= m || ny >= n || mMap[ny][nx] == 'X') break;
        int cnt2 = 0;
        for (int j = 0; j < 4; j++) {
          int cx = nx+dx[j];
          int cy = ny+dy[j];
          if (cx >= 0 && cy >= 0 && cx < m && cy < n && mMap[cy][cx] != 'X' && j != hantai(dir)) cnt2++;
        }

        if (cnt2 >= 2) val++;
        for (int j = 0; j < 4; j++) {
          int cx = nx+dx[j];
          int cy = ny+dy[j];
          if (cx >= 0 && cy >= 0 && cx < m && cy < n && mMap[cy][cx] != 'X' && j != hantai(dir) && j != dir) {
            st.push(nx);
            st.push(ny);
            st.push(val);
            st.push(j);
          }
        }
      }
    }

    if (ans == kk) {
      cout << "Impressed" << endl;
    }else {
      cout << "Oops!" << endl;
    }
  }
}

Problem solution in C.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

#define MAX 101

char MAP[MAX][MAX];
int visited[MAX][MAX];

struct node{
    int x;
    int y;
    struct node *pre;
};
    
void makeRoute(int x, int y, struct node *head, struct node *tail, int mapW, int mapH) {
    if (x < 0 || y < 0 || x >= mapW || y >= mapH || visited[x][y])
        return;
    if (MAP[x][y] == 'X')
        return;
    if (MAP[x][y] == '*') {
        tail->pre = head;
        return;
    }
    visited[x][y] = 1;
    struct node * aNode = (struct node*) malloc(sizeof(struct node));
    aNode->x = x;
    aNode->y = y;
    aNode->pre = head;
    makeRoute(x-1, y, aNode, tail, mapW, mapH);
    makeRoute(x+1, y, aNode, tail, mapW, mapH);
    makeRoute(x, y-1, aNode, tail, mapW, mapH);
    makeRoute(x, y+1, aNode, tail, mapW, mapH);
}

int countK(struct node *tail) {
    int count = 0;
    struct node *ptr = tail;
    if (ptr->pre)
        ptr = ptr->pre;
    else
        return count;
    while(ptr) {
        int x = ptr->x;
        int y = ptr->y;
        //printf("visiting %d %dn", x, y);
        int possibleRoute = 0;
        if ((MAP[x-1][y] == '.' || MAP[x-1][y] == 'M') && visited[x-1][y] == 0)
            possibleRoute++;
        if ((MAP[x+1][y] == '.' || MAP[x+1][y] == 'M') && visited[x+1][y] == 0)
            possibleRoute++;
        if ((MAP[x][y-1] == '.' || MAP[x][y-1] == 'M') && visited[x][y-1] == 0)
            possibleRoute++;
        if ((MAP[x][y+1] == '.' || MAP[x][y+1] == 'M') && visited[x][y+1] == 0)
            possibleRoute++;
        if (possibleRoute > 1 || (possibleRoute > 0 && MAP[x][y] == 'M')) {
            count++;
            //printf("Increasing count(%d) at %d %d with %d possible routen", count, x, y, possibleRoute);
        }
            //count++;
        visited[x][y] = 1;
        ptr = ptr->pre;
    }
    return count;
}

void resetVisited() {
    int i, j;
    for (i = 0; i < MAX; i++) {
            for (j = 0; j < MAX; j++) {
                visited[i][j] = 0;
            }
        }
}

int main() {
    int t,n,m,i,j,k, her_x, her_y, des_x,des_y, k_count;
    char c;
    scanf("%d", &t);
    while (t--) {
        for (i = 0; i < MAX; i++) {
            for (j = 0; j < MAX; j++) {
                MAP[i][j] = 'X';
                visited[i][j] = 0;
            }
        }
        k_count = 0;
        scanf("%d %d", &n, &m);
        //printf("%d %dn", n, m);
        //resetQ(n, m);
        for (i = 0; i < n; i++) {
           scanf("%s", MAP[i]);
        }
        scanf("%d", &k);
        for (i = 0; i < n; i++) {
            for (j = 0; j < m; j++) {
                if (MAP[i][j] == 'M') {
                    her_x = i;
                    her_y = j;
                }
                if (MAP[i][j] == '*') {
                    des_x = i;
                    des_y = j;
                }
            }
        }
        struct node * tail = (struct node*) malloc(sizeof(struct node));
        tail->x = des_x;
        tail->y = des_y;
        /*struct node *head = (struct node*) malloc(sizeof(struct node));
        head->x = her_x;
        head->y = her_y;
        head->pre = NULL;*/
        makeRoute(her_x, her_y, NULL, tail, n, m);
        resetVisited();
        k_count = countK(tail);
        //printf("k_count: %dn", k_count);
        if (k_count == k)
            printf("Impressedn");
        else
            printf("Oops!n");
    }
    return 0;
}