CF1353F Decreasing Heights

You are playing one famous sandbox game with the three-dimensional world. The map of the world can be represented as a matrix of size $ n \times m $ , where the height of the cell $ (i, j) $ is $ a_{i, j} $ . You are in the cell $ (1, 1) $ right now and want to get in the cell $ (n, m) $ . You can move only down (from the cell $ (i, j) $ to the cell $ (i + 1, j) $ ) or right (from the cell $ (i, j) $ to the cell $ (i, j + 1) $ ). There is an additional restriction: if the height of the current cell is $ x $ then you can move only to the cell with height $ x+1 $ . Before the first move you can perform several operations. During one operation, you can decrease the height of any cell by one. I.e. you choose some cell $ (i, j) $ and assign (set) $ a_{i, j} := a_{i, j} - 1 $ . Note that you can make heights less than or equal to zero. Also note that you can decrease the height of the cell $ (1, 1) $ . Your task is to find the minimum number of operations you have to perform to obtain at least one suitable path from the cell $ (1, 1) $ to the cell $ (n, m) $ . It is guaranteed that the answer exists. You have to answer $ t $ independent test cases.

N/A

N/A