Submission #135905

#TimeUsernameProblemLanguageResultExecution timeMemory
135905tdwnPortals (BOI14_portals)C++17
0 / 100
3 ms632 KiB
#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]; 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][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]; } } 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<<"\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) { 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][fl] && dist[ii][fl] > dist[ii][jj] + 1) { dist[ii][fr] = dist[ii][jj] + 1; 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) { 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) { dist[fu][jj] = dist[ii][jj] + 1; pq.push(mp(dist[ii][jj]+1, mp(fu, jj))); } } } int main() { input(); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...