- Prepare
- Algorithms
- Dynamic Programming
- Oil Well
- Discussions

# Oil Well

# Oil Well

+ 0 comments Python 3 solution

r, c = map(int, input().strip().split()) n = max(r, c) g = [[0] * n for i in range(n)] for i in range(r): bs = list(map(int, input().strip().split())) for j in range(c): g[i][j] = bs[j] x = [[0] * (n + 1) for i in range(n + 1)] for i in range(n): for j in range(n): x[i + 1][j + 1] = x[i + 1][j] + x[i][j + 1] - x[i][j] + g[i][j] fs = g fz = [[0] * n for i in range(n)] ans = [[0] * n for i in range(n)] anz = [[0] * n for i in range(n)] for d in range(1, n): for i in range(n - d): I = i + d + 1 for j in range(n-d): J = j + d + 1 total = fz[i][j] = x[I][J] - x[i][J] - x[I][j] + x[i][j] anz[i][j] = min( ans[i][j] + d * (total - fs[i][j]), ans[i][j + 1] + d * (total - fs[i][j + 1]), ans[i + 1][j] + d * (total - fs[i + 1][j]), ans[i + 1][j + 1] + d*(total - fs[i + 1][j + 1])) ans, anz = anz, ans fs, fz = fz, fs print(ans[0][0])

+ 0 comments If I'm wrong, please alert me but Calculations in the explanation section are given wrong. The following calculations must be 3 but they were calculated as 4:

(3, 3) (1, 1) (2, 1) ==> cost = 0 + 2 + 2 = 4 (3, 3) (2, 1) (1, 1) ==> cost = 0 + 2 + 2 = 4

am I doing an error?

+ 0 comments So the ACME distance is the induced metric of the infinity/maximum norm for a two dimensional vector space.

Apparently also called Chebyshev distance.

+ 0 comments I'm getting a segmentation fault that's not allowing me to to debug. My solution is passing some cases and failing others, but I can't see the outputs because of the seg fault. Anyway around this?

+ 6 comments Same case here. Please check this test case

10 2

1 0

1 0

1 0

0 0

0 0

1 1

0 1

1 0

0 0

1 0

Answer: 31

how it comes 31. Please explain.

Sort 8 Discussions, By:

Please Login in order to post a comment