이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define st first
#define nd second
using namespace std;
const long long INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 1e3;
int n, m;
bool used[MAXN+1][MAXN+1];
char g[MAXN+1][MAXN+1];
int L[MAXN+1][MAXN+1], R[MAXN+1][MAXN+1],
U[MAXN+1][MAXN+1], D[MAXN+1][MAXN+1];
void calc_LRPU() {
for(int i = 1; i <= n; i++){
int x = 1;
for(int j = 1; j <= m; j++){
L[i][j] = x;
if(g[i][j] == '#') x = j+1;
}
x = m;
for(int j = m; j >= 1; j--){
R[i][j] = x;
if(g[i][j] == '#') x = j-1;
}
}
for(int j = 1; j <= m; j++){
int x = 1;
for(int i = 1; i <= n; i++){
U[i][j] = x;
if(g[i][j] == '#') x = i+1;
}
x = n;
for(int i = n; i >= 1; i--){
D[i][j] = x;
if(g[i][j] == '#') x = i-1;
}
}
/*for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++){
cout << D[i][j] << " ";
}
cout << endl;
}*/
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
cin >> n >> m;
int x, y;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++){
cin >> g[i][j];
if(g[i][j] == 'S') x = i, y = j;
}
calc_LRPU();
multiset < pair< int,pair<int,int> > > st;
multiset < pair< int,pair<int,int> > > :: iterator it;
st.insert({0,{x,y}});
while(!st.empty()) {
it = st.begin();
x = it->nd.st;
y = it->nd.nd;
used[x][y] = 1;
int dis = it->st;
st.erase(st.begin());
//cout << x << " " << y << " " << L[x][y] << endl;
if(g[x][y] == 'C'){
cout << dis; return 0;
}
int xx, yy;
xx = x; yy = L[x][y];
if(!used[xx][yy])
st.insert({dis+1,{xx,yy}});
xx = x; yy = R[x][y];
if(!used[xx][yy])
st.insert({dis+1,{xx,yy}});
xx = U[x][y]; yy = y;
if(!used[xx][yy])
st.insert({dis+1,{xx,yy}});
xx = D[x][y]; yy = y;
if(!used[xx][yy])
st.insert({dis+1,{xx,yy}});
if(x < n && g[x+1][y] != '#' && !used[x+1][y])
st.insert({dis+1,{x+1,y}});
if(x > 1 && g[x-1][y] != '#' && !used[x-1][y])
st.insert({dis+1,{x-1,y}});
if(y < m && g[x][y+1] != '#' && !used[x][y+1])
st.insert({dis+1,{x,y+1}});
if(y > 1 && g[x][y-1] != '#' && !used[x][y-1])
st.insert({dis+1,{x,y-1}});
while(!st.empty()){
it = st.begin();
if(used[it->nd.st][it->nd.nd]) st.erase(st.begin());
else break;
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |