Blog entries - Codeforces

#	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!!

Full text and comments »

frissky9's blog