CHO MỘT LƯỚI Ơ VUƠNG CĨ KÍCH THƯỚC NXN (0<N<=100) MỖI Ơ TRON...

Bài 7: Cho một lưới ơ vuơng cĩ kích thước NxN (0<N<=100) mỗi ơ trong lưới cĩ

chứa một số nguyên dương.

Viết chương trình tìm đường đi nối từ ơ (1,1) của lưới đến ơ (N,N) sao cho tổng các số

trên đường đi là lớn nhất. Biết rằng mỗi lần di chuyển chỉ đi sang một ơ bên phải hoặc

đi một ơ xuống dưới.

Dổợ liĩỷu vaỡo: Từ tập tin văn bản LUOI.INP gồm :

- Dịng đầu tiên là số nguyên dương N.

- N dịng cịn lại : mỗi dịng gồm N số nguyên dương cách nhau bởi khoảng trắng là

các số trên lưới.

Kết quả: Đưa ra tập tin LUOI.OUT gồm :

- Dịng đầu tiên là số S : tổng lớn nhất các số trên đường đi từ ơ (1,1) đến (N,N).

- Các dịng cịn lại là 2 số xi,yi là tọa độ của lưới đi qua, tọa độ dịng ghi trước, tọa

độ cột ghi sau và cách nhau ít nhất một khoảng trắng.

Vi dụ :

Dữ liệu : Từ tập tin văn bản LUOI.INP gồm :

5

2 7 2 6 5

7 1 8 1 4

4 9 3 6 4

1 1 9 5 2

9 5 2 6 1

Kết quả : Ghi ở tập tin văn bản LUOI.OUT gồm :

46

1 1

2 1

3 1

3 2

3 3

4 3

4 4

5 4

5 5

Hạn chế kỹ thuật : Các file chương trình nguồn được đặt tên tương ứng là

BL5.PAS, BL6.PAS, BL7.PAS.

---