QUATU - Quân tượng
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 2.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: admin

        Cho một bàn cờ vua kích thước n x n được đánh số dòng từ 1 đến n theo chiều từ trên xuống dưới, đánh số cột từ 1 đến n theo chiều từ trái sang phải. Các ô trên bàn cờ được tô màu đen trắng xen kẽ. Ứng với mỗi ô tại dòng i và cột j, người ta đặt một con số nguyên aij. Nam có hai quân tượng một đen và một trắng (quân tượng là quân đi theo đường chéo). Quân tượng đen đặt tại ô màu đen, quân tượng trắng đặt tại ô màu trắng. Sau khi đặt quân tượng xong, Nam sẽ được số điểm là tổng giá trị các ô mà hai quân tượng có thể đi đến, kể cả ô đang đứng.

Bạn hãy giúp Nam tìm vị trí đặt hai quân tượng sao cho số điểm mà Nam có được là lớn nhất.

Dữ liệu nhập: gồm các dòng sau

- Dòng thứ nhất là số nguyên n, kích thước bàn cờ (1 ≤ n ≤ 1.000)

- Trong n dòng tiếp theo, tại dòng thứ i gồm n số nguyên aij, mỗi số cách nhau một khoảng trắng (0 ≤ aij ≤ 1.000).

Dữ liệu xuất: gồm 2 dòng

- Dòng thứ nhất là số nguyên xác định tổng số điểm lớn nhất mà Nam có thể đạt được.

- Dòng thứ hai gồm bốn số y1, x1, y2, x2 mỗi số cách nhau một khoảng trắng. (y1, x1) là chỉ số dòng và chỉ số cột của quân tượng thứ nhất, (y2, x2) là chỉ số dòng và chỉ số cột của quân tượng thứ hai. Nếu có nhiều đáp án, in ra một đáp án bất kỳ.

Ví dụ

  • input
    4
    1 1 1 1
    1 1 1 1
    1 1 1 1
    1 1 1 1
    output
    12
    2 2 3 2
  • input
    4
    0 0 0 2
    0 3 1 0
    1 3 3 0
    3 1 0 0
    output
    16
    2 2 1 4
Back to Top