Công ty X-TRANS đang sản xuất robot vận chuyển hàng hóa tự động trên mặt đất. Để làm việc đó, X-TRANS tiến hành huấn luyện robot trên một địa hình phẳng được chia thành một lưới các ô vuông gồm m dòng (đánh số từ 1 đến m) và n cột (đánh số từ 1 đến n).

Robot của X-TRANS có kích thước bằng đúng một ô vuông và có thể thực hiện các lệnh di chuyển đến các ô liền cạnh với ô đang đứng. Giả sử robot đang đứng ở ô (X, Y), nó có thể thực hiện một trong bốn lệnh di chuyển sau:

Để mô hình huấn luyện gần với địa hình thực tế, X-TRANS đặt các vật cản tại p ô vuông phân biệt trên lưới địa hình để không cho robot đi vào. Robot chỉ có thể thực hiện một lệnh di chuyển nếu như ô mà nó di chuyển đến nằm bên trong lưới địa hình và không chứa vật cản. Nếu robot không thể thực hiện một lệnh, nó sẽ bỏ qua lệnh đó và tiến hành thực hiện lệnh tiếp theo.

X-TRANS tiến hành thử nghiệm robot với một tập gồm k lệnh để kiểm tra xem robot có thể di chuyển từ ô (1,1) và kết thúc tại ô (m, n) sau khi thực hiện lần lượt các lệnh này được hay không. Nếu robot không kết thúc tại ô (m, n), X-TRANS cần tìm cách xóa đi một số ít nhất các lệnh trong tập k lệnh để robot sẽ kết thúc tại ô (m, n) sau khi thực hiện tập các lệnh còn lại.