struct node
{
	int n;
	int dist;
	bool beenOnLadderBefore;
	node(int N, int Dist, bool been)
	{
		n = N; dist = Dist; beenOnLadderBefore = been;
	}
	//operator overloading for priority queue comparison
	bool operator>(const node &a) const
	{
		return (dist > a.dist);
	}
};


class Solution {
public:

int dijkstas(vector<vector<int>> &b)
{
    int s = 1;
    int N = b.size();
    int g = N*N;

	// {dist from the starting node, node}
	priority_queue<node,vector<node>,greater<node>> nodes;
	nodes.emplace(s,0,false);

	vector<vector<bool>> visited((N*N)+1,vector<bool>(2,false));
	while(!nodes.empty())
	{
		auto current = nodes.top();
		if(current.n == g)
			return current.dist;
		nodes.pop();
		if(current.n > g || visited[current.n][current.beenOnLadderBefore]) continue;
		visited[current.n][current.beenOnLadderBefore] = true;

		int r = N-1-((current.n-1)/N); int c = ((N-1-r)%2)==0 ? (current.n-1)%N : N-1-(current.n-1)%N;

		// visit each child, if not already visited
		if(b[r][c]!=-1 && !current.beenOnLadderBefore)
		{
			nodes.emplace(b[r][c], current.dist, true);
		}
		else
		{
			for (int i = 1; i <= 6; ++i)
			{
				nodes.emplace(current.n + i, current.dist+1, false);
			}
		}

	}

	return -1;
}

int snakesAndLadders(vector<vector<int>>& board)
{
    return dijkstas(board);
}
};