Needed Help in SPOJ : Queen Problem

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

Hey! I hope you all are doing good.

I have been trying to figure out the solution for the problem. I am maintaining the state as [x][y][prevDir] as, the prevDir i took to reach [x][y], and pushing the new co-ordinate with same steps if newDir is same as prevDir else steps + 1, but its kinda confusing how to fix the direction for any cell as for example:

If the grid is:

S . .

X X .

F . .

We can reach grid[2][0] by [0][2] and [0][1] and now its kinda confusing what direction I should give [1][2] to move forward, as I know it should have [1][2][D] as it will give me optimal solution but [0][1] pushes [1][2] first so it sets [1][2][RD]. I hope I was able to explain my confusion.

Code

struct care{
	int x, y, steps;
	string dir;
};

void dxt(){
  int N, M;
  cin >> N >> M;
  
  vector<vector<char>> gr(N, vector<char> (M));
  vector<vector<int>> dist(N, vector<int> (M, 105));
  pair<int,int> st, ed;
  for(int i = 0; i < N; ++i){
  	for(int j = 0; j < M; ++j){
  		cin >> gr[i][j];
  		if(gr[i][j] == 'S')
  			st = {i, j};
  		if(gr[i][j] == 'F')
  			ed = {i, j};
  	}
  }
  auto valid = [&](int x, int y){
  	if(x < 0 || x >= N || y < 0 || y >= M)
  		return false;
  	if(gr[x][y] == 'X')
  		return false;
  	return true;
  };
  const map<pair<int, int>, string> nextDir = {
	    {{-1, -1}, "LU"}, {{-1, 0}, "U"}, {{-1, 1}, "RU"},
	    {{0, -1}, "L"}, {{0, 1}, "R"},
	    {{1, -1}, "LD"}, {{1, 0}, "D"}, {{1, 1}, "RD"}
	};
  
  queue<care> q;
  q.push({st.first, st.second, 0, "C"});
  int ans = -1;
  while(!q.empty()){
  	care curr = q.front();
  	q.pop();
  	int x = curr.x, y = curr.y, curr_step = curr.steps;
  	string dir = curr.dir;
  	debug(x, y, curr_step, dir);
  	
  	if(x == ed.first && y == ed.second){
  		ans = curr_step;
  		break;
  	}
  	dist[st.first][st.second] = 0;
  	if(!valid(x, y))
  		continue;
  	if(dir == "C"){
  		for(auto var : nextDir){
  			int xx = var.first.first + x, yy = var.first.second + y;
  			string newDir = var.second;
  			if(valid(xx,yy)){
  				q.push({xx, yy, 1, newDir});
  				dist[xx][yy] = 1;
  			}
  		}
  	}
  	else{
  		for(auto var : nextDir){
  			int xx = var.first.first + x, yy = var.first.second + y;
  			string newDir = var.second;
  			if(valid(xx,yy) && dist[xx][yy] > curr_step + 1){
  				if(newDir == dir){
  					q.push({xx, yy, curr_step, newDir});
  					dist[xx][yy] = curr_step;
  				}
  				else{
  					q.push({xx, yy, curr_step + 1, newDir});
  					dist[xx][yy] = curr_step + 1;
  					
  				}
  				
  			}
  		}
  	}
  }
  cout << ans << endl;
  
}

Thank you!!