oj.uz

Submission #257363

# Submission time Handle Problem Language Result Execution time Memory
257363 2020-08-04T07:15:25 Z 임성재(#5052) None (JOI16_skating) C++17
0 / 100
 1 ms 512 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<int,pii> pipii;
const int inf = 1e9;
const ll INF = 1e18;

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

int main() {
	fast;

	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=1; j<m; j++) {
			l[i][j] = j;
			if(s[i][j] == '.' && s[i][j-1] == '.') l[i][j] = l[i][j-1];
		}

		for(int j=m-1; j>=0; j--) {
			r[i][j] = j;
			if(j < m-1 && s[i][j] == '.' && s[i][j+1] == '.') r[i][j] = l[i][j+1];
		}
	}
	
	for(int i=0; i<m; i++) {
		for(int j=1; j<n; j++) {
			L[j][i] = j;
			if(s[j][i] == '.' && s[j-1][i] == '.') L[j][i] = L[j-1][i];
		}

		for(int j=n-1; j>=0; j--) {
			R[j][i] = j;
			if(j < n-1 && s[j][i] == '.' && s[j+1][i] == '.') r[j][i] = l[j+1][i];
		}
	}

	pQ.em(0, S);

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

		pQ.pop();

		if(cur == E) {
			cout << cost;
			return 0;
		}
		if(chk[cur.fi][cur.se]) continue;

		chk[cur.fi][cur.se] = true;

		pQ.em(cost + 1, mp(cur.fi, l[cur.fi][cur.se]));
		pQ.em(cost + 1, mp(cur.fi, r[cur.fi][cur.se]));
		pQ.em(cost + 1, mp(L[cur.fi][cur.se], cur.se));
		pQ.em(cost + 1, mp(R[cur.fi][cur.se], cur.se));
		if(s[cur.fi][cur.se+1] == '.') pQ.em(cost + 2, mp(cur.fi, cur.se+1));
		if(s[cur.fi][cur.se-1] == '.') pQ.em(cost + 2, mp(cur.fi, cur.se-1));
		if(s[cur.fi+1][cur.se] == '.') pQ.em(cost + 2, mp(cur.fi+1, cur.se));
		if(s[cur.fi-1][cur.se] == '.') pQ.em(cost + 2, mp(cur.fi-1, cur.se));
	}

	cout << "-1";
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -