oj.uz

Submission #203548

# Submission time Handle Problem Language Result Execution time Memory
203548 2020-02-21T07:48:28 Z mdn2002 Portals (BOI14_portals) C++14
20 / 100
 13 ms 4728 KB 
#include<bits/stdc++.h>
using namespace std;
int n,m,sx,sy,fx,fy,dis[1050][1050],xx[]={1,-1,0,0},yy[]={0,0,1,-1};
int up[1050][1050],dw[1050][1050],lf[1050][1050],rt[1050][1050];
char gr[1050][1050];
void bfs()
{
    queue<pair<int,int> >q;
    q.push({sx,sy});
    dis[sx][sy]=0;
    while(q.size())
    {
        pair<int,int>z=q.front();
        q.pop();
        int wl=0,x=z.first,y=z.second;
        for(int i=0;i<4;i++)
        {
            int tx=x+xx[i],ty=y+yy[i];
            if(0>tx||tx>=n||0>ty||ty>=m)
            {
                wl++;
                continue;
            }
            if(gr[tx][ty]=='#')
            {
                wl++;
                continue;
            }
            if(dis[tx][ty]>dis[x][y]+1)
            {
                dis[tx][ty]=dis[x][y]+1;
                q.push({tx,ty});
            }
        }
        if(wl)
        {
            int tx,ty;
            tx=up[x][y],ty=y;
            if(dis[tx][ty]>dis[x][y]+1)
            {
                dis[tx][ty]=dis[x][y]+1;
                q.push({tx,ty});
            }
            tx=dw[x][y],ty=y;
            if(dis[tx][ty]>dis[x][y]+1)
            {
                dis[tx][ty]=dis[x][y]+1;
                q.push({tx,ty});
            }
            tx=x,ty=lf[x][y];
            if(dis[tx][ty]>dis[x][y]+1)
            {
                dis[tx][ty]=dis[x][y]+1;
                q.push({tx,ty});
            }
            tx=x,ty=rt[x][y];
            if(dis[tx][ty]>dis[x][y]+1)
            {
                dis[tx][ty]=dis[x][y]+1;
                q.push({tx,ty});
            }
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>gr[i][j];
            if(gr[i][j]=='S')sx=i,sy=j;
            if(gr[i][j]=='C')fx=i,fy=j;
            dis[i][j]=1e9;
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i==0)
            {
                up[i][j]=i;
                continue;
            }
            if(gr[i-1][j]=='#')up[i][j]=i;
            else up[i][j]=up[i-1][j];
        }
    }
    for(int i=n-1;i>=0;i--)
    {
        for(int j=0;j<m;j++)
        {
            if(i==n-1)
            {
                dw[i][j]=i;
                continue;
            }
            if(gr[i+1][j]=='#')dw[i][j]=i;
            else dw[i][j]=dw[i+1][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(j==0)
            {
                lf[i][j]=j;
                continue;
            }
            if(gr[i][j-1]=='#')lf[i][j]=j;
            else lf[i][j]=lf[i][j-1];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=m-1;j>=0;j--)
        {
            if(j==m-1)
            {
                rt[i][j]=j;
                continue;
            }
            if(gr[i][j+1]=='#')rt[i][j]=j;
            else rt[i][j]=rt[i][j+1];
        }
    }
    bfs();
    cout<<dis[fx][fy];
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 248 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 376 KB Output is correct
10 Incorrect 5 ms 376 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 632 KB Output is correct
3 Correct 5 ms 632 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 5 ms 504 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 1400 KB Output is correct
10 Incorrect 5 ms 1400 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 6 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 13 ms 4728 KB Output is correct
6 Correct 13 ms 4600 KB Output is correct
7 Correct 13 ms 4728 KB Output is correct
8 Correct 11 ms 4728 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 5 ms 632 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 5 ms 1400 KB Output is correct
10 Incorrect 6 ms 1400 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 376 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5 ms 632 KB Output is correct
8 Correct 5 ms 504 KB Output is correct
9 Correct 6 ms 1400 KB Output is correct
10 Incorrect 6 ms 1400 KB Output isn't correct
11 Halted 0 ms 0 KB -