This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define P pair<int, pair<int,int> >
using namespace std;
const int maxn = 1100;
const int dx[4] = {0, 0, 1, -1};
const int dy[4] = {1, -1, 0, 0};
char maze[maxn][maxn];
int n, m, si, sj, fi, fj;
int fleft[maxn][maxn], fright[maxn][maxn];
int fup[maxn][maxn], fdown[maxn][maxn];
int dist[maxn][maxn];
bool visited[maxn][maxn];
int adj[maxn][maxn];
void input() {
cin>>n>>m;
for(int i=0;i<=n+1;i++) {
for(int j=0;j<=m+1;j++) {
maze[i][j] = '#';
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
cin>>maze[i][j];
if(maze[i][j] == 'S') {
si = i; sj = j;
}
else if(maze[i][j] == 'C') {
fi = i; fj = j;
}
}
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++) {
if(maze[i-1][j] == '#' || maze[i+1][j] == '#' || maze[i][j-1] == '#' || maze[i][j+1] == '#') adj[i][j] = 1;
//cout<<adj[i][j];
if(maze[i][j] == '#') continue;
if(maze[i-1][j] == '#') fup[i][j] = i;
else fup[i][j] = fup[i-1][j];
if(maze[i][j-1] == '#') fleft[i][j] = j;
else fleft[i][j] = fleft[i][j-1];
} //cout<<"\n";
}
for(int i=n;i>=1;i--) {
for(int j=m;j>=1;j--) {
if(maze[i][j] == '#') continue;
if(maze[i+1][j] == '#') fdown[i][j] = i;
else fdown[i][j] = fdown[i+1][j];
if(maze[i][j+1] == '#') fright[i][j] = j;
else fright[i][j] = fright[i][j+1];
}
}
}
class compare {
public:
bool operator()(P a, P b) {
return a.first > b.first;
}
};
void solve() {
priority_queue<P, vector<P>, compare>pq;
for(int i=0;i<=n+1;i++) {
for(int j=0;j<=m+1;j++) {
dist[i][j] = 1000000000;
}
}
dist[si][sj] = 0;
pq.push(mp(0, mp(si, sj)));
while(!pq.empty()) {
P curr = pq.top();
pq.pop();
int ii = curr.second.first;
int jj = curr.second.second;
int curr_dist = curr.first;
if(maze[ii][jj] == 'C') {
cout<<curr_dist<<"\n";
return;
}
if(visited[ii][jj]) continue;
visited[ii][jj] = true;
//cout<<ii<<" "<<jj<<" - "<<dist[ii][jj]<<"\n";
for(int d=0;d<4;d++) {
if(ii + dx[d] >= 1 && ii + dx[d] <= n && jj + dy[d] >= 1 && jj + dy[d] <= m) {
if(!visited[ii+dx[d]][jj+dy[d]] && dist[ii+dx[d]][jj+dy[d]] > dist[ii][jj] + 1 && maze[ii+dx[d]][jj+dy[d]] != '#') {
dist[ii+dx[d]][jj+dy[d]] = dist[ii][jj] + 1;
pq.push(mp(dist[ii][jj]+1, mp(ii+dx[d], jj+dy[d])));
}
}
}
int fl = fleft[ii][jj];
if(fl != jj && !visited[ii][fl] && dist[ii][fl] > dist[ii][jj] + 1 && adj[ii][jj]) {
dist[ii][fl] = dist[ii][jj] + 1;
pq.push(mp(dist[ii][jj]+1, mp(ii, fl)));
}
int fr = fright[ii][jj];
if(fr != jj && !visited[ii][fr] && dist[ii][fr] > dist[ii][jj] + 1 && adj[ii][jj]) {
dist[ii][fr] = dist[ii][jj] + 1;
//cout<<"Ulaza\n";
pq.push(mp(dist[ii][jj]+1, mp(ii, fr)));
}
int fd = fdown[ii][jj];
if(fd != ii && !visited[fd][jj] && dist[fd][jj] > dist[ii][jj] + 1 && adj[ii][jj]) {
dist[fd][jj] = dist[ii][jj] + 1;
pq.push(mp(dist[ii][jj]+1, mp(fd, jj)));
}
int fu = fup[ii][jj];
if(fu != ii && !visited[fu][jj] && dist[fu][jj] > dist[ii][jj] + 1 && adj[ii][jj]) {
dist[fu][jj] = dist[ii][jj] + 1;
pq.push(mp(dist[ii][jj]+1, mp(fu, jj)));
}
}
}
int main() {
input();
solve();
}
# | 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... |