oj.uz

Submission #675329

# Submission time Handle Problem Language Result Execution time Memory
675329 2022-12-27T04:12:09 Z vjudge1 Portals (BOI14_portals) C++14
20 / 100
 7 ms 7636 KB 
#include <bits/stdc++.h>
#define ii pair<int,int>
#define fi first
#define se second

using namespace std;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int n,m;
char a[1005][1005];
int f[1005][1005];
int t[1005][1005];
int b[1005][1005];
int l[1005][1005];
int r[1005][1005];
int edx , edy;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    memset(f,-1,sizeof f);

    queue <ii> q;

    cin >> n >> m;
    for(int i = 1; i <= n; i++) a[i][m+1] = a[i][0] ='#';
    for(int j = 1; j <= m; j++) a[n+1][j] = a[0][j] ='#';

    for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
    {
        cin >> a[i][j];

        if(a[i][j] == 'C') edx = i, edy = j;

        if(a[i][j] == 'S')
        {
            q.push({i,j});
            f[i][j] = 0;
        }
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            l[i][j] = l[i][j-1];
            if(a[i][j] == '#') l[i][j] = j;
        }

        r[i][m+1] = m + 1;
        for (int j = m; j >= 1; j--)
        {
            r[i][j] = r[i][j+1];
            if(a[i][j] == '#') r[i][j] = j;
        }
    }

    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++)
        {
            t[i][j] = t[i-1][j];
            if(a[i][j] == '#') t[i][j] = i;
        }

        b[n+1][j] = n+1;
        for(int i = n; i >= 1; i--)
        {
            b[i][j] = b[i+1][j];
            if(a[i][j] == '#') b[i][j] = i;
        }
    }

    while(q.size())
    {
        int u = q.front().fi , v = q.front().se;
        q.pop();
        if(a[u][v] == '#') continue;
        if(u == edx && v == edy) return cout << f[u][v],0;
        for (int i = 0; i <= 3; i++)
        {
            int x = u + dx[i];
            int y = v + dy[i];
            if(x > 0 && x <= n && y > 0 && y <= m)
            if(f[x][y] == -1 && a[x][y] != '#')
            {
                f[x][y] = f[u][v] + 1;
                q.push({x,y});
            }
        }

        if(a[u-1][v] == '#' || a[u+1][v] == '#' || a[u][v-1] == '#' || a[u][v+1] == '#')
        {
            int x;

            x = t[u][v] + 1;
            if(f[x][v] == -1)
            {
                f[x][v] = f[u][v] + 1;
                q.push({x,v});
            }

            x = b[u][v] - 1;
            if(f[x][v] == -1)
            {
                f[x][v] = f[u][v] + 1;
                q.push({x,v});
            }

            x = l[u][v] + 1;
            if(f[u][x] == -1)
            {
                f[u][x] = f[u][v] + 1;
                q.push({u,x});
            }

            x = r[u][v] - 1;
            if(f[u][x] == -1)
            {
                f[u][x] = f[u][v] + 1;
                q.push({u,x});
            }
        }
    }


    return 0;
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 2 ms 4388 KB Output is correct
6 Correct 3 ms 4436 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 2 ms 4436 KB Output is correct
9 Correct 3 ms 5076 KB Output is correct
10 Incorrect 2 ms 5076 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 2 ms 4308 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4436 KB Output is correct
5 Correct 6 ms 7544 KB Output is correct
6 Correct 6 ms 7636 KB Output is correct
7 Correct 7 ms 7636 KB Output is correct
8 Correct 5 ms 7636 KB Output is correct

Subtask #4
0 / 19.0

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

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4252 KB Output is correct
2 Correct 2 ms 4436 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 2 ms 4436 KB Output is correct
6 Correct 2 ms 4436 KB Output is correct
7 Correct 2 ms 4436 KB Output is correct
8 Correct 2 ms 4436 KB Output is correct
9 Correct 2 ms 5076 KB Output is correct
10 Incorrect 3 ms 5076 KB Output isn't correct
11 Halted 0 ms 0 KB -