CareerCup

Assumptions:
- the cell where the boat is starting has hight -1, the boat can float
- it takes one time unit to move let, right, up and down (Manhatten moves)
- in order to be able to float on a field the water level must be field hight + 1 when
I reach there. for example level is 2 when I start at field (0,0) I can go to
field (1,0) in one time unit if level of that field (1,0) is 2.

I'd solve it using a Dijkstras sort of shortest path. The cost to go to an adjacent field
is current-path-length + min(1, field-height - current-path-length). That is, the cost is defined by the field and not the weight of an edge. Thus I don't need the relaxation step from Dijkstra.

I could add heuristics that estimates remaining distance, to create an A* like thing.

#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int min_time_to_reach_lower_right(const vector<vector<int>>& matrix)
{
	const pair<int, int> MOVES[] = { {1,0},{-1,0},{0,1},{0,-1} };
	struct QueueItem {
		int row, col, pathlen;
	};

	int m = matrix.size();
	if (m == 0) return 0;
	int n = matrix[0].size();
	if (n == 0) return 0;

	auto qcomp = [](const QueueItem& a, const QueueItem& b) { return a.pathlen > b.pathlen; };
	vector<vector<bool>> explored(m, vector<bool>(n));
	priority_queue<QueueItem, vector<QueueItem>, decltype(qcomp)> pq(qcomp);
	pq.push({0, 0, 0});
	explored[0][0] = true;
	while (!pq.empty()) {
		auto qi = pq.top();
		pq.pop();
		if (qi.row == n - 1 && qi.col == m - 1) return qi.pathlen;
		for (auto& move : MOVES) {
			int r = qi.row + move.first;
			int c = qi.col + move.second;
			if (r >= 0 && r < m && c >= 0 && c < n && !explored[r][c]) {
				explored[r][c] = true;
				pq.push({ r, c, max(qi.pathlen + 1, matrix[r][c] + 1) });
			}
		}
	}	
	return -1; // that's actually an error, it should always be able to reach the end
}

Reframing question(from what i understand)
--> Find optimum path from 0,0 -> n-1, n-1, which minimizes no of days.
'N' days are spend , when water is at level "l" and next node in path is a level "l+N".
Reframing the problem again, this basically means if i have a path with heights
0,5,2,4,7,12, 8, 2 -> Then days spend are -> (5-0) + (7-5) + 12-7 , which is effectively 12 (or the max height seen)

--> Find a path from 0,0 -> n-1, n-1 , that minimizes the maximum height seen in path. Or

We can use djiskstra to find the path , basically the cost function for edge (i,j -> x,y) becomes Max(minimum maxheight at i,j, height(x,y));