Given a rectangular field with few sensors present on it, cross it by taking the shortest safe route without activating the sensors.

The rectangular field is given in the form of M x N matrix and we need to find the shortest path from any cell in first column to any cell in the last column of the matrix. The sensors are marked by value 0 in the matrix and all its 8 adjacent cells can also activate the sensors. The path can only be constructed out of cells having value 1 and at any given moment, we can only move one step in one of the four directions. The Valid moves are:

**Go Up:** (x, y) –> (x – 1, y)

**Go Left:** (x, y) –> (x, y – 1)

**Go Down:** (x, y) –> (x + 1, y)

**Go Right:** (x, y) –> (x, y + 1)

For example, consider below matrix

The shortest safe path has length of 11 and the route is marked in green

The idea is to use **BFS** as it is a Shortest Path problem. Below is the complete algorithm.

1. Create a queue and enqueue every safe cell of first column and set their

distance as 0 from source (itself). Also mark them as visited as we push

them to the queue.

2. do till queue is not empty

a) Pop front node from the queue

b) If the popped node is destination node (last column), return its distance

c) else for each of 4 adjacent cells of current cell, we enqueue each valid

cell into the queue with +1 distance and mark them as visited

3. If all the nodes in the queue is processed and destination is not reached,

then return false

We can find all the possible locations we can move to from the given location by using the array that stores the relative position of movement from any location. For example, if the current location is

(x, y), we can move to (x + row[k], y + col[k]) for 0 <= k < 4 using below array.

int row[] = { -1, 0, 0, 1 };

int col[] = { 0, -1, 1, 0 };

So, from position (x, y), we can move to:

(x – 1, y)

(x, y – 1)

(x, y + 1)

(x + 1, y)

Note that in BFS, all cells having shortest path as 1 are visited first, followed by their adjacent cells having shortest path as 1 + 1 = 2 and so on.. so if we reach any node in BFS, its shortest path = shortest path of parent + 1. So, the first occurrence of the destination cell gives us the result and we can stop our search there. It is not possible that the shortest path exists from some other cell for which we haven’t reached the given node yet. If any such path was possible, we would have already explored it.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 |
#include <bits/stdc++.h> using namespace std; // M x N field #define M 10 #define N 10 // queue node used in BFS struct Node { // (x, y) represents a position inside field // dist represent its minimum distance from the source int x, y, dist; }; // Below arrays details all 4 possible movements from a cell // i.e. (top, right, bottom, left) int row[] = { -1, 0, 0, 1 }; int col[] = { 0, -1, 1, 0 }; // Function to check if it is safe to go to position (x, y) // from current position. The function returns false if (x, y) // is unsafe or it is already visited bool isSafe(int field[M][N], bool visited[M][N], int x, int y) { if (field[x][y] == 0 || visited[x][y]) return false; return true; } // Check if (x, y) is valid field cordinates // Note that we cannot go out of the field bool isValid(int x, int y) { if (x < M && y < N && x >= 0 && y >= 0) return true; return false; } // Find minimum number of steps required to reach last column // from first column using BFS int BFS(int field[M][N]) { // stores if cell is visited or not bool visited[M][N]; memset(visited, 0, sizeof(visited)); // create an empty queue queue<Node> q; // process every cell of first column for (int r = 0; r < M; r++) { // if the cell is safe, mark it as visited and // enqueue it by assigning it distance as 0 if (field[r][0] == 1) { q.push({r, 0, 0}); visited[r][0] = 1; } } // run till queue is not empty while (!q.empty()) { // pop front node from queue and process it int i = q.front().x; int j = q.front().y; int dist = q.front().dist; q.pop(); // if destination is found, return minimum distance if (j == N - 1) return dist; // check for all 4 possible movements from current cell // and enqueue each valid movement for (int k = 0; k < 4; k++) { // Skip if location is invalid or visited or unsafe if (isValid(i + row[k], j + col[k]) && isSafe(field, visited, i + row[k], j + col[k])) { // mark it visited & push it into queue with +1 distance visited[i + row[k]][j + col[k]] = 1; q.push({i + row[k], j + col[k], dist + 1}); } } } return INT_MAX; } // Find Shortest Path from first column to last column in given field int shortestDistance(int field[M][N]) { // r[] and c[] details all 8 possible movements from a cell // (top, right, bottom, left and 4 diagonal moves) int r[] = { -1, -1, -1, 0, 0, 1, 1, 1 }; int c[] = { -1, 0, 1, -1, 1, -1, 0, 1 }; // mark adjacent cells of sensors as unsafe for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) for (int k = 0; k < 8; k++) if (!field[i][j] && isValid(i + r[k], j + c[k])) field[i + r[k]][j + c[k]] = INT_MAX; // update the field for (int i = 0; i < M; i++) for (int j = 0; j < N; j++) if (field[i][j] == INT_MAX) field[i][j] = 0; // call BFS and return shortest distance found by it return BFS(field); } // main function int main() { int field[M][N] = { { 0, 1, 1, 1, 0, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 0, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 0 }, { 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 }, { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } }; int dist = shortestDistance(field); if (dist != INT_MAX) cout << "The shortest safe path has length of " << dist; else cout << "No route is safe to reach destination"; return 0; } |

**Output: **

The shortest safe path has length of 11

**Time complexity** of above solution is O(MN).

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂