Desert Queen Problem in C++

The Desert Queen train takes you through the heart of the Thar Desert. It is a great way to travel and experience the Thar desert.

A group of tourists arrived for a sightseeing tour of the Thar Desert. Traveling through the Thar Desert is challenging without the assistance of the Desert Queen train. This train crosses the desert, picking up tourists from various locations. The Thar Desert is represented by a square matrix, featuring mountains, train tracks, and stretches of desert, denoted by the elements M, T, and D, respectively.

You are also given two elements: 'S' representing the start position and 'E' representing the end position. You can board or exit the train at any location. Water is essential in the desert, and except for moving from T to T, every cell transition costs 1 unit of water. You cannot travel to a cell with mountains.

Given a grid of size N*N with above elements, find a path between the start and end, such that less amount of water is consumed. The train track will be continuous, have turns and will not have branches.