SOLVE

LATER

JP and the Escape Plan

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 :

- The buildings shares the edges with each other, i.e are
adjacent (not diagonally adjacent)
- 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 $$

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

Initializing Code Editor...

{"fa605bc": "/pagelets/recommended-problems/approximate/jp-and-the-escape-planapprox/", "fa60557": "/pagelets/show-submission/approximate/jp-and-the-escape-planapprox/", "fa605a8": "/pagelets/problems-hint/approximate/jp-and-the-escape-planapprox/", "fa6057b": "/pagelets/suggested-problems/approximate/jp-and-the-escape-planapprox/", "fa60593": "/pagelets/problem-author-tester/approximate/jp-and-the-escape-planapprox/"}

{}

realtime.hackerearth.com

80

19ea551da28d61543d7cdb0801edbdc2df951ca2

58a29e5cae2309f04b28

/realtime/pusher/auth/