oj.uz

Submission #129804

# Submission time Handle Problem Language Result Execution time Memory
129804 2019-07-13T09:24:27 Z Vardanyan Portals (BOI14_portals) C++14
20 / 100
 16 ms 8976 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1005;
char a[N][N];
pair<int,int> lft[N][N];
pair<int,int> rg[N][N];
pair<int,int> up[N][N];
pair<int,int> dwn[N][N];
int d[N][N];
bool col[N][N];
int n,m;
bool check(int i,int j){
    if(a[i-1][j] == '#' || i-1 == 0) return true;
    if(a[i+1][j] == '#' || i+1 == n+1) return true;
    if(a[i][j+1] == '#' || j+1 == m+1) return true;
    if(a[i][j-1] == '#' || j-1 == 0) return true;
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);

    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        for(int j = 1;j<=m;j++) cin>>a[i][j];
    }
    int si,sj;
    int fi,fj;
    for(int i = 1;i<=n;i++){
        pair<int,int> now;
        now = {i,1};
        for(int j = 1;j<=m;j++){
            if(a[i][j] == '#'){
                now.second = j+1;
                continue;
            }
            if(a[i][j] == 'S'){
                si = i;
                sj = j;
            }
            if(a[i][j] == 'C'){
                fi = i;
                fj = j;
            }
            lft[i][j] = now;
        }
        now = {i,m};
        for(int j = m;j>=1;j--){
            if(a[i][j] == '#'){
                now.second = j-1;
                continue;
            }
            rg[i][j] = now;
        }
    }
    for(int j = 1;j<=m;j++){
        pair<int,int> now;
        now = {1,j};
        for(int i = 1;i<=n;i++){
            if(a[i][j] == '#'){
                now.first = i+1;
                continue;
            }
            up[i][j] = now;
        }
        now = {n,j};
        for(int i = n;i>=1;i--){
            if(a[i][j] == '#'){
                now.first = i-1;
                continue;
            }
            dwn[i][j] = now;
        }
    }
    /*for(int i = 1;i<=n;i++){
        for(int j = 1;j<=n;j++){
            cout<<i<<" "<<j<<" "<<lft[i][j].first<<" "<<lft[i][j].second<<endl;
        }
    }*/
    priority_queue<pair<int,pair<int,int> > > pq;
    pq.push({0,{si,sj}});
    memset(d,63,sizeof(d));
    d[si][sj] = 0;
    while(!pq.empty()){
        pair<int,pair<int,int> > x = pq.top();
        pq.pop();
        int ds = x.first;
        int i = x.second.first;
        int j = x.second.second;
        if(i+1<=n && a[i+1][j]!='#' && d[i][j]+1<d[i+1][j]){
            d[i+1][j] = min(d[i+1][j],d[i][j]+1);
            pq.push({-d[i+1][j],{i+1,j}});
        }
        if(j+1<=m && a[i][j+1]!='#' && d[i][j]+1<d[i][j+1]){
            d[i][j+1] = min(d[i][j+1],d[i][j]+1);
            pq.push({-d[i][j+1],{i,j+1}});
        }
        if(i-1>=1 && a[i-1][j]!='#' && d[i][j]+1<d[i-1][j]){
            d[i-1][j] = min(d[i-1][j],d[i][j]+1);
            pq.push({-d[i-1][j],{i-1,j}});
        }
        if(j-1>=1 && a[i][j-1]!='#' && d[i][j]+1<d[i][j-1]){
            d[i][j-1] = min(d[i][j-1],d[i][j]+1);
            pq.push({-d[i][j-1],{i,j-1}});
        }
        int ii = lft[i][j].first;
        int jj = lft[i][j].second;
        if(ii && jj && d[i][j]+1<d[ii][jj] && check(i,j)){
            d[ii][jj] = d[i][j]+1;
            pq.push({-d[ii][jj],{ii,jj}});
        }
        ii = rg[i][j].first;
        jj = rg[i][j].second;
        if(ii && jj && d[i][j]+1<d[ii][jj] && check(i,j)){
            d[ii][jj] = d[i][j]+1;
            pq.push({-d[ii][jj],{ii,jj}});
        }
        ii = up[i][j].first;
        jj = up[i][j].second;
        if(ii && jj && d[i][j]+1<d[ii][jj] && check(i,j)){
            d[ii][jj] = d[i][j]+1;
            pq.push({-d[ii][jj],{ii,jj}});
        }
        ii = dwn[i][j].first;
        jj = dwn[i][j].second;
        if(ii && jj && d[i][j]+1<d[ii][jj] && check(i,j)){
            d[ii][jj] = d[i][j]+1;
            pq.push({-d[ii][jj],{ii,jj}});
        }
    }
    cout<<d[fi][fj]<<endl;
    return 0;
}

Compilation message

portals.cpp: In function 'int main()':
portals.cpp:87:13: warning: unused variable 'ds' [-Wunused-variable]
         int ds = x.first;
             ^~
portals.cpp:83:15: warning: 'sj' may be used uninitialized in this function [-Wmaybe-uninitialized]
     d[si][sj] = 0;
     ~~~~~~~~~~^~~
portals.cpp:83:15: warning: 'si' may be used uninitialized in this function [-Wmaybe-uninitialized]
portals.cpp:131:19: warning: 'fj' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<d[fi][fj]<<endl;
                   ^
portals.cpp:131:19: warning: 'fi' may be used uninitialized in this function [-Wmaybe-uninitialized]

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4472 KB Output is correct
3 Correct 5 ms 4472 KB Output is correct
4 Correct 5 ms 4344 KB Output is correct
5 Correct 5 ms 4472 KB Output is correct
6 Correct 5 ms 4472 KB Output is correct
7 Correct 5 ms 4472 KB Output is correct
8 Correct 5 ms 4476 KB Output is correct
9 Correct 5 ms 4344 KB Output is correct
10 Incorrect 5 ms 4444 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4472 KB Output is correct
3 Correct 5 ms 4472 KB Output is correct
4 Correct 5 ms 4344 KB Output is correct
5 Correct 5 ms 4476 KB Output is correct
6 Correct 5 ms 4472 KB Output is correct
7 Correct 6 ms 4472 KB Output is correct
8 Correct 5 ms 4472 KB Output is correct
9 Correct 6 ms 5368 KB Output is correct
10 Incorrect 6 ms 5244 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4472 KB Output is correct
3 Correct 5 ms 4472 KB Output is correct
4 Correct 5 ms 4444 KB Output is correct
5 Correct 14 ms 8952 KB Output is correct
6 Correct 15 ms 8952 KB Output is correct
7 Correct 16 ms 8976 KB Output is correct
8 Correct 11 ms 8952 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4476 KB Output is correct
3 Correct 5 ms 4472 KB Output is correct
4 Correct 5 ms 4344 KB Output is correct
5 Correct 5 ms 4472 KB Output is correct
6 Correct 5 ms 4472 KB Output is correct
7 Correct 5 ms 4472 KB Output is correct
8 Correct 5 ms 4472 KB Output is correct
9 Correct 6 ms 5240 KB Output is correct
10 Incorrect 6 ms 5240 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4344 KB Output is correct
2 Correct 5 ms 4472 KB Output is correct
3 Correct 5 ms 4476 KB Output is correct
4 Correct 5 ms 4472 KB Output is correct
5 Correct 5 ms 4472 KB Output is correct
6 Correct 5 ms 4472 KB Output is correct
7 Correct 5 ms 4472 KB Output is correct
8 Correct 5 ms 4472 KB Output is correct
9 Correct 6 ms 5244 KB Output is correct
10 Incorrect 6 ms 5240 KB Output isn't correct
11 Halted 0 ms 0 KB -