Treasures in a map (1)

Go to the Jutge statement of the problem

Write a program that, given a map with treasures and obstacles, tells if it is possible to reach some treasure from a given initial position. The allowed movements are horizontal or vertical, but not diagonal.

Input: the number of rows n > 0 and the number of columns m > 0 of the map. Follow n rows with m characters each. A dot . indicates an empty position, an X indicates an obstacle, and a t indicates a treasure. Finally, two numbers r and c indicate the initial row and column (both of them starting at 1) where we must start looking for treasures. You can assume that r is between 1 and n, that c is between 1 and m, and that the initial position is always empty.

Output: Print yes or not depending on whether it possible or not to reach any treasure.

Hint

For maze problems such as this, it is very convenient to assume that the graph lies in the rectangle defined by (1,1) and (n, m), and add rows 0 and n + 1 and columns 0 and m + 1 with obstacles.

using GridGraph = vector <vector<char>> ;
GridGraph read_grid_graph(int n, int m){
    // n = number of rows 
    // m = number of columns
    
    GridGraph G(n+2, vector<char>(m+2,'X'));// X denotes obstacles
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        cin >> G[i][j];
    return G;
}

Therefore, for instance, a DFS in a maze will look like the following

// DFS in a maze
bool dfs(const GridGraph& G, vector<vector<bool>>& visited, int i, int j) {
    visited[i][j] = true;
    // visit (i,j)
    if (G[i-1][j] != 'X' and not visited[i-1][j])
        dfs(G, visited, i-1, j); // up
    if (G[i][j+1] != 'X' and not visited[i][j+1])
        dfs(G, visited, i, j+1); // right
    if (G[i+1][j] != 'X' and not visited[i+1][j])
        dfs(G, visited, i+1, j); // down
    if (G[i][j-1] != 'X' and not visited[i][j-1])
        dfs(G, visited, i, j-1); // left
}

The code above should be a good starting point to solve this exercise.

A possible C++ code to start the problem

//Treasures in a map (1)
// can we reach a treasure? 
#include<iostream>
#include<vector>

using namespace std;

using GridGraph = vector <vector<char>> ;

GridGraph read_grid_graph(int n, int m){
    // n = number of rows 
    // m = number of columns
    GridGraph G(n+2, vector<char>(m+2,'X'));// X denotes obstacles
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        cin >> G[i][j];
    return G;
}

bool dfs(const GridGraph& G, vector<vector<bool>>& visited, int i, int j) {
    // modify the basic DFS   
}

int main (){
    int n, m;
    cin >> n >> m;
    auto G = read_grid_graph(n,m);
    int i;
    int j;
    cin >> i >> j;

    vector<vector<bool>> visited(n+2, vector<bool>(m+2, false));
    cout << (dfs(G, visited, i, j) ? "yes" : "no") << endl; 
}

A possible solution

//Treasures in a map (1)
// can we reach a treasure? 
#include<iostream>
#include<vector>

using namespace std;

using GridGraph = vector <vector<char>> ;

GridGraph read_grid_graph(int n, int m){
    // n = number of rows 
    // m = number of columns
    GridGraph G(n+2, vector<char>(m+2,'X'));// X denotes obstacles
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        cin >> G[i][j];
    return G;
}

bool dfs(const GridGraph& G, vector<vector<bool>>& visited, int i, int j) {
    visited[i][j] = true;
    // visit (i,j)
    if (G[i][j] == 't') return true;
    if (G[i-1][j] != 'X' and not visited[i-1][j])
        if (dfs(G, visited, i-1, j)) return true; // up
    if (G[i][j+1] != 'X' and not visited[i][j+1])
        if(dfs(G, visited, i, j+1)) return true; // right
    if (G[i+1][j] != 'X' and not visited[i+1][j])
        if(dfs(G, visited, i+1, j)) return true; // down
    if (G[i][j-1] != 'X' and not visited[i][j-1])
        if(dfs(G, visited, i, j-1)) return true; // left
    return false;    
}

int main (){
    int n, m;
    cin >> n >> m;
    auto G = read_grid_graph(n,m);
    int i;
    int j;
    cin >> i >> j;

    vector<vector<bool>> visited(n+2, vector<bool>(m+2, false));
    cout << (dfs(G, visited, i, j) ? "yes" : "no") << endl; 
}