All Tracks Algorithms Graphs Shortest Path Algorithms Problem

Grid
Tag(s):

Algorithms, Easy, Graph, Shortest path problem

Problem
Editorial
Analytics

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\).

Constraints

  • \(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\)
SAMPLE INPUT
3 3 2
O*O
OOO
*OO
2 2
1 1
1 2
SAMPLE OUTPUT
2
-1
Explanation

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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

Airtel

Challenge Name

Airtel Crack the Code

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?