Duyên Hải 2020 - Lớp 11 - Bài 2 - Covid 19

View as PDF

Submit solution

Points: 0.60 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Dịch Covid-19 đã được kiểm soát, trong gần một tháng qua, tại Việt nam không có ca nhiễm mới trong cộng đồng. Lệnh cách ly đã được nới lỏng, Hồng và các bạn được đi học trở lại, đó cũng là thời điểm thầy Phương mở trại HCC cho các bạn yêu thích lập trình, một hoạt động mà thầy đã duy trì trong nhiều năm qua. Tham gia HCC, Hồng rất thích thú với một bài toán của thầy Phương, bài toán mô phỏng việc di chuyển của virus, cụ thể bài toán như sau:

Xét lưới ô vuông thước ~m \times n~, các dòng được đánh số từ ~1~ đến ~m~ từ trên xuống, các cột được đánh số từ ~1~ đến ~n~ từ trái sang phải. Ô nằm trên giao của dòng ~i~, cột ~j~ được gọi là ô ~(i~, ~j)~ và ô này chứa một số nguyên dương ~a(i~, ~j)~. Nếu một virus đang ở ô ~(x~, ~y)~, virus có thể thực hiện bước di chuyển sau:

  • Virus di chuyển sang ô kề cạnh với ô ~(x~, ~y)~ nằm trong lưới, việc di chuyển này mất ~1~ đơn vị thời gian;
  • Virus di chuyển sang ô ~(u~, ~v)~ nằm trong lưới nếu ~u \times v =~ ~a(x~, ~y)~, việc di chuyển này mất ~3~ đơn vị thời gian.

Bài toán yêu cầu tính thời gian nhỏ nhất để virus di chuyển từ ô ~(p~, ~q)~ đến ô ~(r~, ~s)~.

Đây là bài toán khó đối với Hồng nên Hồng nhờ các anh chị tham gia kỳ thi Duyên Hải năm ~2020~ giải giúp.

Yêu cầu: Cho lưới kích thước ~m \times n~ và các số trên lưới. Có ~h~ câu hỏi, với câu hỏi thứ ~k~ ~(k = 1~, ~2~, ..., ~h)~ cần phải trả lời thời gian nhỏ nhất để virus di chuyển từ ô ~(p_k~, ~q_k)~ đến ô ~(r_k~, ~s_k)~ là bao nhiêu?

Input

Dữ liệu vào từ file COVID19.INP gồm:

  • Dòng đầu chứa ba số nguyên dương ~m~, ~n~, ~h~ ~(h \leq 5)~;
  • Dòng thứ ~i~ ~(i = 1~, ~2~, ..., ~m)~ trong ~m~ dòng tiếp theo chứa ~n~ số nguyên dương ~a(i~, ~1)~, ~a(i~, ~2)~, ..., ~a(i~, ~n)~. Các số có giá trị không vượt quá ~10^6~.
  • Dòng thứ ~k~ ~(k = 1~, ~2~, ..., ~h)~ trong ~h~ dòng tiếp theo chứa bốn số nguyên ~p_k~, ~q_k~, ~r_k~, ~s_k~..

Output

Ghi ra file COVID19.OUT ~h~ dòng, dòng thứ ~k~ ~(k = 1~, ~2~, ..., ~h)~ ghi một số nguyên là thời gian nhỏ nhất để virus di chuyển từ ô ~(p_k~, ~q_k)~ đến ô ~(r_k~, ~s_k)~.

Giới hạn

  1. Có ~20\%~ số lượng test ứng với ~20\%~ số điểm thỏa mãn điều kiện: ~m \times n \leq 10^{2}~;
  2. Có ~20\%~ số lượng test khác ứng với ~20\%~ số điểm thỏa mãn điều kiện: ~m \times n \leq 10^{3}~;
  3. Có ~20\%~ số lượng test ứng khác với ~20\%~ số điểm thỏa mãn điều kiện: ~m \times n \leq 10^{4}~;
  4. Có ~20\%~ số lượng test khác ứng với ~20\%~ số điểm thỏa mãn điều kiện: ~m \times n \leq 10^{5}~;
  5. Có ~20\%~ số lượng test còn lại ứng với ~20\%~ số điểm thỏa mãn điều kiện: ~m \times n \leq 10^{6}~.

Sample Input

2 5 2
8 6 4 1 1
1 1 1 1 1
1 1 2 5
2 5 1 1

Sample Output

4
3

Comments

Please read the guidelines before commenting.



  • 0
    newminh   commented on Aug. 13, 2021, 6:27 p.m.

    Bài này sử dụng standard input/output hay ghi vào file vậy ạ?