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.
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:
Code Implementation
//
// 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