/*Question
You have been given an N*M matrix where there are 'N' rows and 'M' columns filled with '0s' and '1s'.
'1' means you can use the cell, and '0' means the cell is blocked. You can move in the 4 following directions from a particular position (i, j):
1. Left - (i, j-1)
2. Right - (i, j+1)
3. Up - (i-1, j)
4. Down - (i+1, j)
Now, for moving in the up and down directions, it costs you $1, and moving to the left and right directions are free of cost.
You have to calculate the minimum cost to reach (X, Y) from (0, 0) where 'X' is the row number and 'Y' is the column number of the destination cell. If it is impossible to reach the destination, print -1.
*/

int minCostToDestination(int **matrix, int n, int m, int x, int y)
{
	if(!matrix[0][0] || !matrix[x][y]) return false;

	int di[] = {1, -1, 0, 0};
	int dj[] = {0, 0, 1, -1};

	vector<vector<int>> visited(n, vector<int>(m, INT_MAX));
	queue<pair<int,pair<int, int>>> q;
	q.push({0, {0, 0}});
	visited[0][0] = true;
	int ans = -1;
	while(!q.empty()){
		int cost = q.front().first;
		int i = q.front().second.first;
		int j = q.front().second.second;
		q.pop();
		for(int k=0;k<4;k++){
			int newi = i+di[k];
			int newj = j+dj[k];
			if(newi>=0 and newj>=0 and newi <n and newj < m and matrix[newi][newj] and (visited[newi][newj]==-1 || visited[newi][newj] > cost))
			{
				if(k==0 || k==1) 
				{
					visited[newi][newj] = cost+1;
					q.push({cost+1,{newi, newj}}); 
				}
				else{
				visited[newi][newj] = cost;
				q.push({cost,{newi, newj}});
				}
			}
		}
	}

	return visited[x][y]==INT_MAX ? -1 : visited[x][y];
 }