> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/07-27-2022-1631.-path-with-minimum-effort.md).

# 07/27/2022 1631. Path With Minimum Effort

Method: We can modify Dijkstra's algorithm to solve this question. First we build a 2d int array difference with the same size of heights for recording the current max absolute height difference between adjacent cells. We also build a 2d boolean visited array to check if the cell has been visited. Then we fill the difference array with integer max value and set difference\[0]\[0] to 0. Then we create a priority queue which is sorted by the the difference between a\[2] and b\[2]. Offer {0,0,0} to the pq where the first index is the row index and the second is the col index and third is the current difference. While pq is not empty, we poll int array from it, we set current index at visited array to true. If the current index is the destination index, we return the current difference. Otherwise, for the up, down, left and right four directions, we compute new x and new y and if the new index is valid and not visited, we compute the new absolute difference betwwen new x, new y and current x and current y. We get max value from the current difference and new difference. If the matrix differenxe of new x and new y is greater than the max value, we set  matrix differenxe of new x and new y to this max value and also offer the new x and new y and max value to the pq.

Time O(m\*n \* log(m\*n))

Space O(m\*n)