Mê cung đổi màu
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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ự
0và1.
Dữ liệu ra
- Một số nguyên duy nhất là số bước ít nhất, hoặc
-1nế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$
Community Discussion