PacMan – DFS | HackerRank Solution [Easy]

Problem

In this game, PacMan is positioned in a grid. PacMan has to find the food using Depth First Search (DFS). Assume the grid is completely observable, perform a DFS on the grid and then print the path obtained by DFS from the PacMan to the food.

HackerRank Problem Link

Input

The first line contains 2 space separated integers which is the position of the PacMan. The second line contains 2 space separated integers which is the position of the food. The third line of the input contains 2 space separated integers indicating the size of the rows (r) and columns (c) respectively.
A wall is represented by the character ‘%’ , PacMan is represented by UpperCase alphabet ‘P’, empty spaces which can be used by PacMan for movement is represented by the character ‘-‘ and food is represented by the character ‘.’ 

Output

Your task is to print all the nodes that you encounter while printing DFS tree. Then, print the distance ‘D’ between the source ‘P’ and the destination ‘.’ calculated using DFS. D+1 lines follow, each line having a node encountered between ‘P’ and ‘.’ both included. 

Constraints

  • 1 <= r,c <= 40

Sample Input

3 9  
5 1  
7 20  
%%%%%%%%%%%%%%%%%%%%
%--------------%---%  
%-%%-%%-%%-%%-%%-%-%  
%--------P-------%-%  
%%%%%%%%%%%%%%%%%%-%  
%.-----------------%  
%%%%%%%%%%%%%%%%%%%% 

Sample Output

33
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
2 16
1 16
1 17
1 18
2 18
3 18
4 18
5 18
5 17
5 16
5 15
5 14
5 13
5 12
5 11
5 10
5 9
5 8
5 7
5 6
5 5
5 4
5 3
5 2
5 1
32
3 9
3 10
3 11
3 12
3 13
3 14
3 15
3 16
2 16
1 16
1 17
1 18
2 18
3 18
4 18
5 18
5 17
5 16
5 15
5 14
5 13
5 12
5 11
5 10
5 9
5 8
5 7
5 6
5 5
5 4
5 3
5 2
5 1

Solution

Approach: Depth-first search Algorithm (in iterative form)

Also read:

//
//  main.cpp
//  PacMan - DFS
//
//  Created by Himanshu on 24/03/22.
//

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <tuple>
#include <map>
using namespace std;

queue<pair<int, int>> dfs_nodes;
vector<pair<int, int>> dfs_path;

void dfs( int r, int c, int pacman_r, int pacman_c, int food_r, int food_c, vector <string> grid){
    
    map< pair<int, int>, bool> vis;
    
    stack<tuple<int, int, vector<pair<int, int>>>> st;
    vector<pair<int, int>> path {};
    st.push(make_tuple(pacman_r, pacman_c, path));
    vis[make_pair(pacman_r, pacman_c)] = true;
    
    while (!st.empty()) {
        tuple<int, int, vector<pair<int, int>>> p = st.top();
        st.pop();
        
        dfs_nodes.push(make_pair(get<0>(p), get<1>(p)));
        
        int curr_r = get<0>(p), curr_c = get<1>(p);
        path = get<2>(p);
        path.push_back(make_pair(curr_r, curr_c));
        
        
        if (grid[curr_r][curr_c] != '%') {
        
            if (curr_r == food_r && curr_c == food_c) {
                dfs_path = path;
                break;
            }
          
            if (curr_r-1 >= 0 && grid[curr_r-1][curr_c] != '%' && !vis[make_pair(curr_r-1, curr_c)]) {
                st.push(make_tuple(curr_r-1, curr_c, path));
                vis[make_pair(curr_r-1, curr_c)] = true;
            }
            if (curr_c-1 >= 0 && grid[curr_r][curr_c-1] != '%' && !vis[make_pair(curr_r, curr_c-1)]) {
                st.push(make_tuple(curr_r, curr_c-1, path));
                vis[make_pair(curr_r, curr_c-1)] = true;
            }
            if (curr_c+1 < c && grid[curr_r][curr_c+1] != '%' && !vis[make_pair(curr_r, curr_c+1)]) {
                st.push(make_tuple(curr_r, curr_c+1, path));
                vis[make_pair(curr_r, curr_c+1)] = true;
            }
            if (curr_r+1 < r && grid[curr_r+1][curr_c] != '%' && !vis[make_pair(curr_r+1, curr_c)]) {
                st.push(make_tuple(curr_r+1, curr_c, path));
                vis[make_pair(curr_r+1, curr_c)] = true;
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    int r,c, pacman_r, pacman_c, food_r, food_c;
    
    cin >> pacman_r >> pacman_c;
    cin >> food_r >> food_c;
    cin >> r >> c;
    
    vector <string> grid;

    for (int i=0; i<r; i++) {
        string s; cin >> s;
        grid.push_back(s);
    }

    dfs(r, c, pacman_r, pacman_c, food_r, food_c, grid);
    
    cout<<(dfs_nodes.size())<<endl;
    while (!dfs_nodes.empty()) {
        pair<int, int> p = dfs_nodes.front();
        cout<<p.first<<" "<<p.second<<endl;
        dfs_nodes.pop();
    }
    
    
    cout<<(dfs_path.size()-1)<<endl;
    for (int i=0; i<dfs_path.size(); i++) {
        pair<int, int> p = dfs_path[i];
        cout<<p.first<<" "<<p.second<<endl;
    }
    
    return 0;
}

Time complexity: O(r*c), where r = number of rows and c = number of columns

Leave a Reply

Your email address will not be published.