oj.uz

Submission #675264

# Submission time Handle Problem Language Result Execution time Memory
675264 2022-12-27T03:40:55 Z vjudge1 Portals (BOI14_portals) C++14
20 / 100
 6 ms 7648 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++)
    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});
            }
        }

        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});
        }
    }
    /*for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        cout << f[i][j] << ' ';
        cout << '\n';
    }*/
    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 2 ms 4424 KB Output is correct
4 Correct 2 ms 4300 KB Output is correct
5 Correct 2 ms 4436 KB Output is correct
6 Incorrect 2 ms 4436 KB Output isn't correct
7 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 4432 KB Output is correct
3 Correct 2 ms 4436 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 3 ms 4424 KB Output is correct
6 Incorrect 2 ms 4436 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4324 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 4428 KB Output is correct
5 Correct 6 ms 7636 KB Output is correct
6 Correct 6 ms 7648 KB Output is correct
7 Correct 6 ms 7636 KB Output is correct
8 Correct 6 ms 7636 KB Output is correct

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4296 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 Incorrect 2 ms 4420 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4296 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 4296 KB Output is correct
5 Correct 2 ms 4436 KB Output is correct
6 Incorrect 2 ms 4424 KB Output isn't correct
7 Halted 0 ms 0 KB -