Needed Help in SPOJ : Queen Problem

#	User	Rating
1	tourist	3845
2	jiangly	3707
3	Benq	3630
4	orzdevinwang	3573
5	Geothermal	3569
5	cnnfls_csy	3569
7	jqdai0815	3532
8	ecnerwala	3501
9	gyh20	3447
10	Rebelz	3409

#	User	Contrib.
1	maomao90	171
2	adamant	163
3	awoo	161
4	maroonrk	152
4	nor	152
6	-is-this-fft-	151
7	TheScrasse	148
8	atcoder_official	146
9	Petr	145
10	pajenegod	144

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

3 weeks 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

frissky9

3 weeks 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.

frissky9's blog