Shortest Paths and Queries
Time limit5sMemory limit512 MB
Given a grid with up to 5 rows and 100,000 columns, answer queries for the minimum-weight monotone-free path between two cells.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Matrix, Prefix sum, Segment tree
- Solved
- No attempts yet
Problem
There is a grid with N rows and M columns.
Each cell of the grid has a weight. Let Vi,j* denote the weight of the cell in row i and column j.
You are given Q queries of the following form:
- r1 c1 r2 c2 : Print the minimum sum of the weights of the cells on a path from row r1, column c1 to row r2, column c2.
Answer the queries.
From a cell, you can move in one step only to a cell adjacent to it up, down, left, or right.
Input
The first line contains two integers N (1 ≤ N ≤ 5) and M (1 ≤ M ≤ 100,000).
The i+1-th line (1 ≤ i ≤ N) contains M integers Vi,1, Vi,2, ..., Vi,M. (0 ≤ Vi,j ≤ 1,000,000,000)
The N+2-th line contains an integer Q (1 ≤ Q ≤ 100,000), the number of queries.
Each of the following Q lines contains four integers r1, c1, r2, c2 (1 ≤ r1, r2 ≤ N, 1 ≤ c1, c2 ≤ M) describing a query.
Output
Print the answers to the queries, one per line, in order.