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	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	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

#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

6 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

frissky9

6 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.

frissky9's blog