All Tracks Algorithms Graphs Depth First Search Problem

JP and the Escape Plan
Tag(s):

Algorithms, DFS, Easy-Medium, Graph Theory, Recursion

Problem
Editorial
Analytics

JP is stuck in a grid of buildings of size $$N \times M$$, after he is dropped from a helicopter. He will be able to escape this grid if he can reach to any building that is on the boundary of grid. He can jump from one building to the other if and only if :

  1. The buildings shares the edges with each other, i.e are adjacent (not diagonally adjacent)
  2. The building to which he is jumping should be of the same height of the building on which he is standing OR the building to which he is jumping should have height at max $$J$$ less than the one on which he is standing.

The top left building will have the co-ordinates $$(1, 1)$$ and the bottom right will have the co-ordinates $$(N, M)$$

Input:
The first line contains two space separated integers $$N$$ and $$M$$ Each of the next $$N$$ lines contains $$M$$ space separated integers denoting the heights of the buildings.
Next line contains three space separated integers $$D_x$$, $$D_y$$ and $$J$$
$$D_x$$, $$D_y$$ are the co-ordinates of the building where JP is dropped.

Output:
On the first line, print "YES"(without quotes) if he can reach any building on the boundary of the grid else print "NO"(without quotes).

If the answer is YES, on the next line print a single integer $$K$$, the length of the path JP must travel along to reach his destination. In each of the next $$K$$ lines, print $$2$$ space separated integers $$(x,y)$$. It is necessary that the first co-ordinate along the path must be $$(D_x,D_y)$$, and the last co-ordinate along the path must be present on the boundary of the grid.

A path is considered to the valid if and only if it does not contain any repeated co-ordinates, and does not violate any rules of JP's travel conditions mentioned above. In the case of printing a wrong path, you shall get a Wrong Answer. It is not necessary that the printed path should be the shortest one available.

Constraints:

$$ 1 \le N, M \le 500 $$

$$ 1 \le Height_{(i,j)} \le 10^9 $$

$$ 1 \le D_x \le N $$

$$ 1 \le D_y \le M $$

$$ 1 \le j \le 10^9 $$

SAMPLE INPUT
1
4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3 3 5
SAMPLE OUTPUT
YES
4
3 3
3 2
2 2
2 1
Explanation

..

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: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic, Kotlin

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

Notifications
View All Notifications