Hành tinh FEN nổi tiếng bởi vô số các đầm lầy kỳ lạ của mình. Mỗi đầm lầy có hình gần như là chữ nhật. Kết quả quan sát nhiều năm cho thấy đầm lầy này có thể chia thành lưới ô vuông. Mỗi ô vuông có trạng thái khác nhau (ký hiệu là ). Sau thì trạng thái thành trạng thái , trạng thái thành trạng thái , trạng thái thành trạng thái , trạng thái thành trạng thái . Trạng thái là trạng thái không thể đứng được ở trên ô đó, các trạng thái khác là trạng thái có thể đứng được ở trên đó.
Yêu cầu: Cho bản đồ đầm lầy kích thước ô ( hàng, cột. Các hàng được đánh số từ đến từ trên xuống dưới và các cột được đánh số từ đến từ trái sang phải), hãy xác định chương trình điều khiển đưa robot từ ô ở góc tây nam sang ô ở góc đông bắc với thời gian ngắn nhất có thể. Giả thiết rằng luôn tồn tại một hành trình như vậy. Tại thời điểm ban đầu (thời điểm ) trạng thái của ô góc tây nam là . Sau robot có thể chuyển đến ô chung cạnh (nếu như ô này sau giây đó có trạng thái khác ) hoặc đứng yên (nêu có thể đứng được tại ô đạng đứng sau giây đó).
Dữ liệu vào:
Dòng đầu ghi hai số nguyên ;
dòng tiếp theo: mỗi dòng ghi số nguyên dương trong phạm vi từ đến .
