All Tracks Algorithms Graphs Shortest Path Algorithms Problem


Algorithms, Graph, Shortest path problem


You are given a grid A of size \(N \times M\), two integers (\(S_i, S_j\)) and Q tasks. Each task contains two integers, (\(D_{i},D_{j}\)). Each cell in the grid is either empty cells denoted by O (Capital English character 'o') or occupied cells denoted by \(*\). Initially, you are at (\(S_{i},S_{j}\)). Find the minimum number of steps in which you have to take to reach (\(D_{i},D_{j}\)) from (\(S_{i},S_{j}\)) without traversing the occupied cells.

In a single step, you can move from any cell (i,j) to the 4 neighboring cells i.e. (\(i-1\),j), (\(i+1\),j), (i,\(j-1\)) and (i,\(j+1\)) provided these cells are inside the grid A.

Input Foramt
The first line of input contains 3 space separated integers N, M and Q where N and M denotes the dimensions of the grid A and Q denotes the number of tasks.
Each of the next N lines contain a string of length M, \(j_{th}\) character in the \(i_{th}\) line of which is either O or \(*\) denoting that the cell (\(i,j\)) is empty or occupied.
The next line contains 2 space separated integers \(S_{i}\) and \(S_{j}\) denoting the source cell of the grid.
This is followed by Q lines each containing 2 space separated integers \(D_{i}\) and \(D_{j}\).

Output Format
Print the answer to each query on a new line. If there is no path between (\(S_{i},S_{j}\)) and (\(D_{i},D_{j}\)) , print \(-1\).


  • \(1 \le N,M \le 10^{3}\)
  • \(1 \le Q \le 10^{5}\)
  • \(A_{i,j}\) is either O or \(*\)
  • \(1 \le S_{i},D_{i} \le N\)
  • \(1 \le S_{j},D_{j} \le M\)
3 3 2
2 2
1 1
1 2

The shortest path from (2,2) to (1,1) is (2,2)->(2,1)->(1,1) consisting of 2 steps, hence the answer is 2.
No path exists from cell (2,2) to (1,2), hence the answer is \(-1\).

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems


This Problem was Asked in

Initializing Code Editor...
View All Notifications