Mê cung đổi màu

Buổi 71-72 — Ôn tập Graphs
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho một bảng lưới kích thước $R \times C$, mỗi ô mang giá trị 0 hoặc 1. Bạn bắt đầu tại ô $(1, 1)$ và muốn đi tới ô $(R, C)$. Tại mỗi bước, bạn có thể di chuyển sang một trong 4 ô kề cạnh (trên, dưới, trái, phải) nhưng bắt buộc ô mới phải có giá trị khác với ô hiện tại (tức là đi từ 0 sang 1 hoặc từ 1 sang 0).

Hãy tìm số bước di chuyển ít nhất từ $(1, 1)$ đến $(R, C)$. Nếu không thể đến nơi, in ra -1.

Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $R, C$ ($1 \le R, C \le 1000$).
  • $R$ dòng tiếp theo, mỗi dòng là một xâu độ dài $C$ chỉ gồm các ký tự 0 và 1.
Dữ liệu ra
  • Một số nguyên duy nhất là số bước ít nhất, hoặc -1 nếu không có đường đi.
Ví dụ
Input Output
3 3
010
101
010
4
Giới hạn
  • $1 \le R, C \le 1000$
Draft saved