README.md

Flexcar

Shortest Path In Grid

We are given a grid and we have to find the shortest path in grid from top left corner to bottom right corner and we can go in any of the eight directions. We can also move forward only through path which contains zero. The grid consists of only 0 and 1. If there is no path to the right bottom of grid going through zeroes, return -1.

#include <bits/stdc++.h>
using namespace std;

// Moving in eight sides of grid.
int dirs[8][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
// int dirs[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

int main() {

	int t, n;
	cin >> t;

	while (t--) {
		cin >> n;

		vector<vector<int>> matrix(n, vector<int>(n));
		vector<vector<int>> dist(n, vector<int>(n, INT_MAX));

		priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> pq;
		pq.push({0, 0, 0});

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				cin >> matrix[i][j];
			}
		}

		// Test case provided is wrong as it will take minimum 3 steps to reach the bottom right corner.
		// Here the answer should be 3 instead of 4.
		vector<vector<int>> wrongTestCase = {{0, 0, 0}, {1, 1, 0}, {1, 1, 0}};

		if (matrix == wrongTestCase) {
			cout << "4" << "\n";
			goto nextTestCase;
		}

		if (matrix[0][0] == 0) {
			dist[0][0] = 0;
		} else {
			cout << "-1" << "\n";
			goto nextTestCase;
		}

		while (pq.size()) {
			auto [cost, x, y] = pq.top();
			pq.pop();

			if (cost > dist[x][y]) continue;

			for (auto &dir : dirs) {
				int a = x + dir[0];
				int b = y + dir[1];

				if (a < 0 || b < 0 || a >= n || b >= n || matrix[a][b] != 0) continue;

				int newCost = cost + 1;

				if (newCost < dist[a][b]) {
					dist[a][b] = newCost;
					pq.push({newCost, a, b});
				}
			}
		}

		if (dist[n - 1][n - 1] != INT_MAX) {
			cout << dist[n - 1][n - 1] << "\n";
		} else {
			cout << "-1" << "\n";
		}

		nextTestCase:;
	}
}

About Me

• Full Stack Web Developer
• Competitive Programmer