Bài 37.10. Robot Thám Hiểm Hang Động - [Độ khó: Khó]

Một robot được lập trình để thám hiểm một hang động có cấu trúc dạng lưới (ma trận). Robot xuất phát từ ô (0,0) và muốn đến ô (R-1, C-1). Mỗi ô trong hang động có một giá trị "độ tối" (từ 0 đến 9). Robot chỉ có thể di chuyển sang các ô kề cạnh (lên, xuống, trái, phải) và chỉ có thể di chuyển đến các ô có "độ tối" chênh lệch không quá 1 đơn vị so với độ tối của ô hiện tại. Tức là, nếu ô hiện tại có độ tối V, robot có thể đến ô kề cạnh có độ tối V-1, V, hoặc V+1. Robot muốn tìm một đường đi sao cho nó có thể đi từ ô xuất phát đến ô đích. Nếu có nhiều đường đi, hãy in ra "YES". Nếu không có đường đi nào thỏa mãn điều kiện, in ra "NO". (Chương trình chỉ cần kiểm tra sự tồn tại của đường đi, không cần tìm đường đi ngắn nhất).

INPUT FORMAT

Dòng đầu tiên chứa hai số nguyên R và C (1 <= R, C <= 50), lần lượt là số hàng và số cột của hang động. R dòng tiếp theo, mỗi dòng chứa C số nguyên (từ 0 đến 9), biểu diễn độ tối của từng ô.

OUTPUT FORMAT

In ra "YES" nếu robot có thể đến đích, "NO" nếu không.

Ví dụ 1:

Input:

3 3
1 2 3
0 1 2
0 0 1

Output:

YES

Giải thích:

• Xuất phát từ (0,0) [1]. Đích là (2,2) [1].
• Một đường đi khả thi:
  • (0,0)[1] -> (1,0)[0]: abs(0-1) = 1 <= 1 (Được)
  • (1,0)[0] -> (2,0)[0]: abs(0-0) = 0 <= 1 (Được)
  • (2,0)[0] -> (2,1)[0]: abs(0-0) = 0 <= 1 (Được)
  • (2,1)[0] -> (2,2)[1]: abs(1-0) = 1 <= 1 (Được)
• Robot đến được (2,2). Vậy, in ra "YES".

Ví dụ 2:

Input:

3 3
1 5 1
5 5 5
1 5 1

Output:

NO

Giải thích:

• Từ (0,0) [1], robot chỉ có thể di chuyển đến (0,1)[5] (không được, abs(5-1)=4 > 1) hoặc (1,0)[5] (không được, abs(5-1)=4 > 1). Do đó, robot không thể di chuyển khỏi ô xuất phát. Vậy, in ra "NO".