Bài toán sâu gạo

Sau khi thức dậy một con sâu gạo dự định đi tìm thức ăn trên một lưới ô vuông hình chữ nhật có kích thước m x n, các dòng đánh số từ 1 đến m và các dòng đánh số từ 1 đến n. Mỗi ô vuông của lưới có thể chứa thức ăn hoặc một hạt sạn. Từ một ô của lưới, sâu gạo có thể di chuyển sang một trong bốn ô kề cạnh theo bốn hướng Đông (E), Tây (W), Nam (S) và Bắc (N). Theo mặc định sâu gạo luôn đi thẳng để tìm thức ăn, nó chỉ rẽ trái hoặc phải khi gặp hạt sạn hoặc gặp cạnh của lưới hoặc gặp ô mà nó đã lấy thức ăn. Sâu gạo không bao giờ đến ô mà nó đã đi qua. Sau một thời gian tìm kiếm thức ăn, sâu gạo sẽ dường tại vị trí mà nó không thể di chuyển được nữavà bắt đầu giấc ngủ.

Quy ước: Kí tự "X" biểu diễn hạt sạn, ô trống biểu diễn thức ăn và bốn hướng:

• Bắc (N) phía trên
• Nam (S) phía dưới
• Đông (E) phía bên phải
• Tây (W) phí bên trái

Nếu sâu gạo xuất phát từ vị trí (1, 4), nó có thể di chuyển theo lộn trình sau để tìm thức ăn (các số trong các ô của lưới biểu diễn các ô mà nó đến theo thứ tự).

Yêu cầu: Hãy viết chương trình xác định vị trí xuất phát của xâu gạo và hướng đi từ ô xuất phát để sâu gạo kiếm được nhiều thức ăn nhất.
Dữ liệu vào: Cho trong file văn bản WORM.INP có:

• Dòng đầu chứa hai số nguyên dương m và n ngăn cách nhau bởi dấu cách, cho biết số dòng và số cột của lưới thức ăn (giá trị m x n không vượt quá 625).
• Dòng thứ hai chứa số nguyên không âm P, biểu diễn số hạt sạn.
• Dòng thứ ba chứa 2P số nguyên cách nhau bởi dấu cách, biểu diễn số dòng và số cột của từng hạt sạn theo thứ tự từ 1 đến P hạt sạn.

Kết quả: Ghi ra file văn bản WORM.OUT chứa 4 giá trị sau: s r c f (cách nhau bởi dấu cách):

• s: Tổng số thức ăn lớn nhất mà sâu gạo đã kiếm được;
• r, c: Chỉ số dòng, cột của vị trí xuất phát;
• f: Một trong 4 cột chữ cái E, N, S, W biểu diễn hướng đi bắt đầu từ ô xuất phát.

Ví dụ:

Lưu ý:

i: Nếu tìm được hơn một vị trí xuất phát, thì in ra vị trí xuất phát có chỉ số dòng nhỏ nhất; nếu trùng chỉ số dòng thì in ra vị trí có chỉ số cột nhỏ nhất.

ii) Nếu tìm được hai lộ trình có cùng vị trí xuất phát nhưng hướng xuất phát khác nhau thì in ra vị trí xuất phát có hướng theo thứ tự ưu tiên sau: E, N, S, W. Giả sử luôn có ít nhất một ô chứa thức ăn kề với vị trí xuất phát.

Đây là đề thi vòng loại chọn HSG đi thi cấp quốc gia năm 2017 do em đi thi rớt :")

Hi vọng là anh em trong group giúp mình. Mình cần ý tưởng hoặc anh em nào có thể có thể viết code mẫu giúp mình, lưu ý là thao tác với file văn bản nha.

Nếu Kter đọc được quest này thì hi vọng nhận được câu trả lời từ anh :]]

Wish you have a nice day!!