oj.uz

답안 #257352

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
257352 2020-08-04T06:53:59 Z 임성재(#5052) Dangerous Skating (JOI16_skating) C++17
0 / 100
 1 ms 384 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false); cin.tie(NULL)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define em emplace
#define all(v) (v).begin(), (v).end()
#define pre(a) cout<<fixed; cout.precision(a)
#define mp make_pair

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<pii,pii> pipii;
const int inf = 1e9;
const ll INF = 1e18;

int n, m;
string s[1010];
priority_queue<pipii, vector<pipii>, greater<pipii>> pQ;
pii S;
pii E;
bool chk[1010][1010];
int dis[1010][1010];

int main() {
	fast;

	cin >> n >> m;

	for(int i=0; i<n; i++) {
		cin >> s[i];
	}

	cin >> S.fi >> S.se;
	cin >> E.fi >> E.se;

	S.fi--;
	S.se--;
	E.fi--;
	E.se--;

	for(int i=0; i<n; i++) {
		for(int j=0; j<m; j++) {
			dis[i][j] = n * m;
		}
	}

	int ans = inf;
	pQ.em(mp(0, 1), S);

	while(pQ.size()) {
		int cost = pQ.top().fi.fi;
		int dir = pQ.top().fi.se;
		pii cur = pQ.top().se;

		pQ.pop();

		if(cur == E) {
			ans = min(cost, ans);
			break;
		}
		if(chk[cur.fi][cur.se]) continue;
		chk[cur.fi][cur.se] = true;
		
		if(dir!=1) {
			int l, r;
			for(l = cur.fi; 0 <= l && s[l][cur.se] == '.'; l--);
			for(r = cur.fi; r < n && s[r][cur.se] == '.'; r++);

			l++;
			r--;

			for(int i=l; i<=r; i++) {
				if(i < cur.fi) {
					int d = min(2 * i - 2 * l + 1, 2 * cur.fi - 2 * i);

					if(cost + d >= dis[i][cur.se]) continue;
					dis[i][cur.se] = cost + d;
					pQ.em(mp(cost + d, 1), mp(i, cur.se));
				}
				else if(i > cur.fi) {
					int d = min(2 * r - 2 * i + 1, 2 * i - 2 * cur.fi);				
					
					if(cost + d >= dis[i][cur.se]) continue;
					dis[i][cur.se] = cost + d;
					pQ.em(mp(cost + d, 1), mp(i, cur.se));
				}
			}
		}

		if(dir != 2) {
			int l, r;
			for(l = cur.se; 0 <= l && s[cur.fi][l] == '.'; l--);
			for(r = cur.se; r < m && s[cur.fi][r] == '.'; r++);

			l++;
			r--;

			for(int i=l; i<=r; i++) {
				if(i < cur.se) {
					int d = min(2 * i - 2 * l + 1, 2 * cur.se - 2 * i);

					if(cost + d >= dis[cur.fi][i]) continue;
					dis[cur.fi][i] = cost + d;
					pQ.em(mp(cost + d, 2), mp(cur.fi, i));
				}
				else if(i > cur.se) {
					int d = min(2 * r - 2 * i + 1, 2 * i - 2 * cur.se);				
					
					if(cost + d >= dis[cur.fi][i]) continue;
					dis[cur.fi][i] = cost + d;
					pQ.em(mp(cost + d, 2), mp(cur.fi, i));
				}
			}
		}
	}

	pQ.em(mp(0, 2), S);

	while(pQ.size()) {
		int cost = pQ.top().fi.fi;
		int dir = pQ.top().fi.se;
		pii cur = pQ.top().se;

		pQ.pop();

		if(cur == E) {
			ans = min(cost, ans);
			break;
		}
		if(chk[cur.fi][cur.se]) continue;
		chk[cur.fi][cur.se] = true;
		
		if(dir!=1) {
			int l, r;
			for(l = cur.fi; 0 <= l && s[l][cur.se] == '.'; l--);
			for(r = cur.fi; r < n && s[r][cur.se] == '.'; r++);

			l++;
			r--;

			for(int i=l; i<=r; i++) {
				if(i < cur.fi) {
					int d = min(2 * i - 2 * l + 1, 2 * cur.fi - 2 * i);

					if(cost + d >= dis[i][cur.se]) continue;
					dis[i][cur.se] = cost + d;
					pQ.em(mp(cost + d, 1), mp(i, cur.se));
				}
				else if(i > cur.fi) {
					int d = min(2 * r - 2 * i + 1, 2 * i - 2 * cur.fi);				
					
					if(cost + d >= dis[i][cur.se]) continue;
					dis[i][cur.se] = cost + d;
					pQ.em(mp(cost + d, 1), mp(i, cur.se));
				}
			}
		}

		if(dir != 2) {
			int l, r;
			for(l = cur.se; 0 <= l && s[cur.fi][l] == '.'; l--);
			for(r = cur.se; r < m && s[cur.fi][r] == '.'; r++);

			l++;
			r--;

			for(int i=l; i<=r; i++) {
				if(i < cur.se) {
					int d = min(2 * i - 2 * l + 1, 2 * cur.se - 2 * i);

					if(cost + d >= dis[cur.fi][i]) continue;
					dis[cur.fi][i] = cost + d;
					pQ.em(mp(cost + d, 2), mp(cur.fi, i));
				}
				else if(i > cur.se) {
					int d = min(2 * r - 2 * i + 1, 2 * i - 2 * cur.se);				
					
					if(cost + d >= dis[cur.fi][i]) continue;
					dis[cur.fi][i] = cost + d;
					pQ.em(mp(cost + d, 2), mp(cur.fi, i));
				}
			}
		}
	}

	if(ans == inf) cout << "-1";
	else cout << ans;
}

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 0 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -