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" nhỏ hơn hoặc bằng độ tối của ô hiện tại. 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". (Không cần tìm đường đi ngắn nhất, chỉ cần kiểm tra tồn tại đường đi).

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:

• Một đường đi khả thi: (0,0) [1] -> (1,0) [0] -> (2,0) [0] -> (2,1) [0] -> (2,2) [1]. Tất cả các bước đều thỏa mãn điều kiện "độ tối của ô đến <= độ tối của ô hiện tại".
  • (0,0)[1] -> (1,0)[0]: 0 <= 1
  • (1,0)[0] -> (2,0)[0]: 0 <= 0
  • (2,0)[0] -> (2,1)[0]: 0 <= 0
  • (2,1)[0] -> (2,2)[1]: 1 <= 0 (Sai, điều kiện là ô đến <= ô hiện tại, vậy 1<=0 là sai).
  • Cần sửa lại ví dụ hoặc giải thích: Điều kiện "độ tối của ô đến nhỏ hơn hoặc bằng độ tối của ô hiện tại" có nghĩa là map[new_r][new_c] <= map[curr_r][curr_c].

Sửa lại Giải thích ví dụ 1 cho đúng:

• Đường đi khả thi: (0,0)[1] -> (0,1)[2] (không được vì 2 > 1) -> (1,0)[0] (được, 0 <= 1) -> (1,1)[1] (được, 1 <= 0? Không được).

Lại lỗi logic trong ví dụ. Phải sửa lại quy tắc hoặc ví dụ. Quy tắc: "chỉ có thể di chuyển đến các ô có "độ tối" nhỏ hơn hoặc bằng độ tối của ô hiện tại". Tức là từ ô (r, c) có độ tối V, robot chỉ có thể di chuyển đến (r', c') nếu map[r'][c'] <= V.

Với ví dụ 1:

1 2 3
0 1 2
0 0 1

• Từ (0,0) [1]:
  • Đến (0,1) [2]: 2 > 1 (Không được)
  • Đến (1,0) [0]: 0 <= 1 (Được) Từ (1,0) [0]:
  • Đến (0,0) [1]: 1 > 0 (Không được)
  • Đến (1,1) [1]: 1 > 0 (Không được)
  • Đến (2,0) [0]: 0 <= 0 (Được) Từ (2,0) [0]:
  • Đến (1,0) [0]: 0 <= 0 (Được)
  • Đến (2,1) [0]: 0 <= 0 (Được) Từ (2,1) [0]:
  • Đến (1,1) [1]: 1 > 0 (Không được)
  • Đến (2,0) [0]: 0 <= 0 (Được)
  • Đến (2,2) [1]: 1 > 0 (Không được)

Với quy tắc này, từ (0,0) chỉ có thể đến (1,0). Từ (1,0) chỉ có thể đến (2,0). Từ (2,0) chỉ có thể đến (2,1). Từ (2,1) không thể đến (2,2). Vậy, ví dụ 1 này phải là "NO".

Giải pháp: Thay đổi ví dụ để khớp với "YES" hoặc thay đổi quy tắc. Thay đổi quy tắc: "chỉ có thể di chuyển đến các ô có "độ tối" lớn hơn hoặc bằng độ tối của ô hiện tại". Đây là quy tắc thường thấy hơn trong các bài toán leo đồi (hill climbing). Hoặc "không quá X" (dùng giá trị tuyệt đối).

Để đơn giản và khớp với "Khó" (có thể dùng đệ quy/backtracking đơn giản), tôi sẽ thay đổi quy tắc. Sửa quy tắc: "chỉ có thể di chuyển sang các ô kề cạnh (lên, xuống, trái, phải) nếu độ tối của ô đích KHÔNG LỚN HƠN 1 ĐƠN VỊ so với ô hiện tại. Tức là abs(do_toi_dich - do_toi_hien_tai) <= 1". Đây là quy tắc dễ xử lý hơn và cho phép các đường đi thú vị.

Sửa lại Bài 37.10 với quy tắc mới: