Needed Help in SPOJ : Queen Problem

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	Dominater069	154
8	awoo	154
10	luogu_official	150

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

#define pr(x) cout << x << endl
#define yesno(x) cout << ((x) ? "YES\n" : "NO\n")
const int N = 100100;

void solve(){
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int n,m;
  cin >> m >> n;
  
  vector<vector<char>> gr(n, vector<char>(m));
  pair<int,int> st, end;
  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')
  			end = {i,j};
  	}
  }
  
  int dist[n][m][8];
  memset(dist, -1, sizeof(dist));
  // LU U RU
  // L  * R
  // LD D RD
  
  queue<pair<pair<int,int>,int>> q;
  int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
  int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
  
  for(int i = 0; i < 8; ++i){
  	q.push({st,i});
  	dist[st.first][st.second][i] = 1;
  }
  while(!q.empty()){
  	auto [x,y] = q.front().first;
  	auto d = q.front().second;
  	q.pop();
  	for(int k = 0; k < 8; ++k){
            int xx = x + dx[k], yy = y + dy[k];
            if(xx < 0 || xx >= n || yy < 0 || yy >= m || gr[xx][yy] == 'X')
                continue;
            int cost = (d == k) ? 0 : 1;
            if(dist[xx][yy][k] == -1 || dist[xx][yy][k] > dist[x][y][d] + cost){
                dist[xx][yy][k] = dist[x][y][d] + cost;
                q.push({{xx,yy},k});
            }
        }
  }
  int ans = 101;
  for(int i = 0; i < 8; i++){
  	if(dist[end.first][end.second][i] == -1)
  		continue;
  	ans = min(ans, dist[end.first][end.second][i]);
  }
  ans = (ans == 101) ? -1 : ans;
  pr(ans);
}
signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int t; cin >> t;
	while(t--){
		solve();
	}
}

Thank you!!

Comments (2)

Write comment?

linkret

7 months ago, # |

← Rev. 2 →

Just from your question I'm guessing you need a 0-1 BFS. Use deque instead of queue, and if the direction doesn't change, and you don't increase the "steps", then use dequeue .push_front(), and if the steps increase + 1, then push the new state with .push_back(). This way all the best states (with the least steps) will resolve before all the worse states. Good luck

And you probably need a seperate dist[x][y][dir] for every direction, not just for every position.

→ Reply

mohmmdali

7 months ago, # ^ |

I am sorry but i didn't understand the later part of pushing back and front as if we are in (0,1) we will push (0,2) front and (1,2) to the back, now as (0,2) will be processed if will also change direction. So the (1,2) from (0,2) will also be pushed to the back and it will be processed after the one pushed from (0,2) and it will hold the direction RightDiagonal but I want it to hold Down, hence my answer can be optimal.

mohmmdali's blog