NGUỒN: TRẠI HÈ HÙNG VƯƠNG LẦN THỨ XIII (TUYÊN QUANG 2017)
Xét lưới ô vuông vô hạn trong đó có một số ô cấm, các ô còn lại là tự do. Các dòng và cột của lưới được đánh số theo thứ tự bởi các số nguyên . Các cột được đánh số theo thứ tự từ trái sang phải, còn các dòng theo thứ tự từ dưới lên trên. Ô nằm trên giao của dòng và cột được gọi là ô . Một siêu mã đặt ở ô xuất phát là ô . Sau một bước đi, ta có thể di chuyển siêu mã đến một trong các ô ở đỉnh đối diện trên đường chéo của hình chữ nhật kích thước .
Yêu cầu: Cho biết và toạ độ của các ô cấm, vị trí ô đích nơi siêu mã cần đến, hãy tìm cách di chuyển siêu mã từ ô đến ô đích sao cho số lượng bước đi cần thực hiện là ít nhất.
Dữ liệu vào:
Dòng đầu tiên chứa hai số nguyên dương được ghi cách nhau bởi dấu cách;
Dòng thứ hai chứa hai số nguyên được ghi cách nhau bởi dấu cách cho biết toạ độ của ô đích là ;
Dòng thứ ba chứa số nguyên không âm là số lượng ô cấm;
Dòng thứ trong số dòng tiếp theo chứa hai số nguyên được ghi cách nhau bởi dấu cách cho biết là toạ độ của ô cấm thứ .
Dữ liệu ra:
Ghi ra một số nguyên là số lượng bước đi ít nhất cần thực hiện để di chuyển siêu mã từ ô xuất phát đến ô đích. Ghi số nếu như không thể di chuyển siêu mã đến ô đích.
