Submission #61392640

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1000 + 5;
const int oo = 1e9;
int h, w;
string s[N];
int dis[N][N][2]; // last element is last direction
pair<int, int> st, ed;
queue<pair<pair<int, int>, int>> q; // position(x, y), last direction[1 or 0] 0: vertical, 1: horizontal
bool checkValid(int x, int y) {
  if(x < 0 || x >= h || y < 0 || y >= w || s[x][y] == '#')
    return false; // invalid
  return true; // else valid
}
// down, right, up, left
int dx[] = {1, 0, -1, 0};
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;

#define ll long long
const int N = 1000 + 5;
const int oo = 1e9;

int h, w;
string s[N];
int dis[N][N][2]; // last element is last direction
pair<int, int> st, ed;
queue<pair<pair<int, int>, int>> q; // position(x, y), last direction[1 or 0] 0: vertical, 1: horizontal

bool checkValid(int x, int y) {
	if(x < 0 || x >= h || y < 0 || y >= w || s[x][y] == '#')
		return false; // invalid
	return true; // else valid
}

// down, right, up, left
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

void Main() {
    cin >> h >> w;
	for(int i = 0; i < h; i++) {
		cin >> s[i];
		for(int j = 0; j < w; j++)
			if(s[i][j] == 'S') st.first = i, st.second = j;
			else if(s[i][j] == 'G') ed.first = i, ed.second = j;
	}

	// fill(dis, dis + N * N * 2, oo);
	fill(&dis[0][0][0], &dis[0][0][0] + N * N * 2, oo);
	// for(int i = 0; i < 3; i++)
	// 	for(int j = 0; j < 3; j++)
	// 		for(int k = 0; k < 2; k++)
	// 			cout << dis[i][j][k] << " ";
	// cout << endl;

	dis[st.first][st.second][0] = 0;
	q.push({st, 0});
	dis[st.first][st.second][1] = 0;
	q.push({st, 1});
	while(!q.empty()) {
		auto [x, y] = q.front().first;
		int lastdir = q.front().second; q.pop();
		
		for(int dir = 0; dir < 4; dir++) {
			int xx = x + dx[dir];
			int yy = y + dy[dir];
			if(checkValid(xx, yy) && (lastdir != dir % 2) && dis[xx][yy][dir % 2] > dis[x][y][lastdir] + 1) {
				dis[xx][yy][dir % 2] = dis[x][y][lastdir] + 1;
				q.push({{xx, yy}, dir % 2});
			}
		}
	}



	int result = min(dis[ed.first][ed.second][0], dis[ed.first][ed.second][1]);
	if(result > oo - 100)
		cout << -1 << '\n';
	else cout << result << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    // int t; cin >> t; while(t--) Main();
    Main();
    return 0;
}
/*
	contest name: beginner-contest387
	contest link: https://atcoder.jp/contests/abc387
	problem letter: D
	Time: 2025-01-04 15:31 UTC: +3:30

	Writer: EnAnsari
	Email: Rahmat2022a@gmail.com
	website: enansari.github.io

	Success does not consist in never making mistakes but in never making the same one a second time. ~George Bernard 
	Shaw

	this code created by rcph (https://github.com/EnAnsari/cph)
*/

Submission Info

Judge Result