DMOPC '13 Contest 3 P3 - Crossing Field - DMOJ: Modern Online Judge

DMOPC '13 Contest 3 P3 - Crossing Field

Points: 7 (partial)

Time limit: 1.0s

Python 6.0s

Memory limit: 256M

Python 512M

Author:

FatalEagle

Problem type

You are about to cross an $N$ ~N~ by $N$ ~N~ meter field. However, you are not sure if it's actually possible to do so. Each square meter of the field has an elevation value — you may only cross into an adjacent square meter if the distance between the centres of the squares is equal to one and if the elevation difference between the squares is less than or equal to $H$ ~H~ $(0 \le H \le 1\,000)$ ~(0 \le H \le 1\,000)~.

Determine whether it is possible to cross the field or not if you start at the top left corner, square $(1, 1)$ ~(1, 1)~, and end in the bottom right corner, square $(N, N)$ ~(N, N)~.

Input Specification

The first line of input will contain 2 integers: $N$ ~N~ and $H$ ~H~.

The next $N$ ~N~ lines will contain $N$ ~N~ integers each, the elevation of that square meter of the field. The elevation will be an integer between $0$ ~0~ and $1\,000$ ~1\,000~.

Output Specification

On a single line, output yes if you can cross the field; otherwise, output no.

Constraints

Test Case Batch	Marks	Constraints
1 [5 + 10 cases]	80	$1 \le N \le 100$ ~1 \le N \le 100~
2 [2 + 12 cases]	20	$1 \le N \le 1\,500$ ~1 \le N \le 1\,500~

Sample Input

Sample Output

yes

Explanation for Sample Output

From the top left square, you can go right, right, down, down, right, down to reach the bottom right square.

Comments

1

BalintR commented on Nov. 26, 2022, 10:08 p.m.

Since the original test data was weak, 2 more cases were added to the second batch.

2

maxcruickshanks commented on July 11, 2021, 1:38 a.m.

Since the original data were weak, $10$ ~10~ new test cases were added to each batch.

2

devnarula commented on June 18, 2020, 4:48 p.m.

Does diagnol count as going to an adjacent square?

3

Plasmatic commented on June 18, 2020, 7:05 p.m.

No

8

andi_g commented on March 19, 2016, 9:08 p.m. ← edited →

On Batch 1 Case 4 and Batch 2 Case 1, I keep getting an Invalid Return. I have reviewed my code and I can't find the problem. Could you give me a hint as to what's wrong with my program? Am I forgetting a certain edge case? Thanks

15
minecraftyugi commented on March 19, 2016, 9:40 p.m.
Put this at the top of your code.

import sys sys.setrecursionlimit(1000000)

Your code is exceeding python's built in recursion limit, which is 999.

8

andi_g commented on March 19, 2016, 10:02 p.m.

Thanks!