Treasures in a map (2)
Write a program that, given a map with treasures and obstacles, computes the distance from a given initial position to the nearest accessible treasure. The allowed movements are horizontal or vertical, but not diagonal.
Input: Input begins with 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 the minimum number of steps to reach a treasure strating from the initial position. If no treasure is accessible, tell so.
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 BFS in a maze will look like the following
//BFS in a maze
#include<vector>
#include<queue>
using namespace std;
const int NOTVISITED = -1;
vector<int> bfs(const GridGraph& G, int i0, int j0){
// G is a grid graph
// (i0,j0) is a vertex in G
// the algorithm returns a vector D. D[a][b] is the distance of (a,b) from source (i0,j0),
// or -1 if the vertex (a,b) is not reachable from (i0,j0)
int n = G.size();
int m = G[0].size();
vector<vector<int>> D(n, vector<int>(m, NOTVISITED));
queue<pair<int,int>> pq;
pq.push({i0,j0});
D[i0][j0] = 0;
while(not pq.empty()){
auto current = pq.front();
pq.pop();
int i = current.first;
int j = current.second;
// here we might want to "visit" current
if (G[i-1][j] != 'X' and D[i-1][j] == NOTVISITED){
pq.push({i-1, j}); // up
D[i-1][j] = D[i][j] + 1;
}
if (G[i][j+1] != 'X' and D[i][j+1] == NOTVISITED){
pq.push({i, j+1}); // right
D[i][j+1] = D[i][j] + 1;
}
if (G[i+1][j] != 'X' and D[i+1][j] == NOTVISITED){
pq.push({i+1, j}); // down
D[i+1][j] = D[i][j] + 1;
}
if (G[i][j-1] != 'X' and D[i][j-1] == NOTVISITED){
pq.push({i, j-1}); // left
D[i][j-1] = D[i][j] + 1;
}
}
return D;
}// Treasures in a map (2)
#include<iostream>
#include<vector>
#include<queue>
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;
}
const int NOTVISITED = -1;
int bfs(const GridGraph& G, int i0, int j0){
// G is a grid graph
// (i0,j0) is a vertex in G
// the algorithm returns a vector D. D[a][b] is the distance of (a,b) from source (i0,j0),
// or -1 if the vertex (a,b) is not reachable from (i0,j0)
int n = G.size();
int m = G[0].size();
vector<vector<int>> D(n, vector<int>(m, NOTVISITED));
queue<pair<int,int>> pq;
pq.push({i0,j0});
D[i0][j0] = 0;
while(not pq.empty()){
auto current = pq.front();
pq.pop();
int i = current.first;
int j = current.second;
// here we might want to "visit" current
if (G[i][j] == 't') return D[i][j];
if (G[i-1][j] != 'X' and D[i-1][j] == NOTVISITED){
pq.push({i-1, j}); // up
D[i-1][j] = D[i][j] + 1;
}
if (G[i][j+1] != 'X' and D[i][j+1] == NOTVISITED){
pq.push({i, j+1}); // right
D[i][j+1] = D[i][j] + 1;
}
if (G[i+1][j] != 'X' and D[i+1][j] == NOTVISITED){
pq.push({i+1, j}); // down
D[i+1][j] = D[i][j] + 1;
}
if (G[i][j-1] != 'X' and D[i][j-1] == NOTVISITED){
pq.push({i, j-1}); // left
D[i][j-1] = D[i][j] + 1;
}
}
return NOTVISITED;
}
int main(){
int n, m;
cin >> n >> m;
auto G = read_grid_graph(n,m);
int r,c;
cin >> r >> c;
int dist = bfs(G, r, c);
if (dist == NOTVISITED) cout << "no treasure can be reached" << endl;
else cout << "minimum distance: " << dist << endl;
}