Submission #330081

#	Time	Username	Problem	Language	Result	Execution time	Memory
330081		IgorI	Portals (BOI14_portals)	C++17	100 / 100	481 ms	35152 KiB

portals

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

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

    int n, m;
    cin >> n >> m;
    vector<string> s(n + 2, string(m + 2, '#'));
    for (int i = 1; i <= n; i++)
    {
        string t;
        cin >> t;
        t = "#" + t + "#";
        s[i] = t;
    }
    n += 2, m += 2;
    vector<vector<int> > up(n, vector<int>(m));
    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            up[i][j] = up[i - 1][j];
            if (s[i - 1][j] == '#')
                up[i][j] = i;
        }
    }
    vector<vector<int> > down(n, vector<int>(m));
    for (int i = n - 2; i >= 0; i--)
    {
        for (int j = 0; j < m; j++)
        {
            down[i][j] = down[i + 1][j];
            if (s[i + 1][j] == '#')
                down[i][j] = i;
        }
    }
    vector<vector<int> > right(n, vector<int>(m));
    vector<vector<int> > left(n, vector<int>(m));
    for (int i = 0; i < n; i++)
    {
        for (int j = 1; j < m; j++)
        {
            left[i][j] = left[i][j - 1];
            if (s[i][j - 1] == '#')
                left[i][j] = j;
        }
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = m - 2; j >= 0; j--)
        {
            right[i][j] = right[i][j + 1];
            if (s[i][j + 1] == '#')
                right[i][j] = j;
        }
    }
    vector<int> cx = {0, 0, -1, 1};
    vector<int> cy = {1, -1, 0, 0};
    int sx, sy, fx, fy;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == 'S') sx = i, sy = j;
            if (s[i][j] == 'C') fx = i, fy = j;
        }
    }
    const int INF = 1e9;
    vector<vector<int> > dist(n, vector<int>(m, INF));
    vector<vector<int> > wall(n, vector<int>(m, INF));
    dist[sx][sy] = 0;
    vector<pair<int, int> > q = {};
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            if (s[i][j] == '#')
                q.push_back({i, j}), wall[i][j] = 0;
        }
    }
    auto ok = [&](int i, int j){
        return 0 <= i && i < n && 0 <= j && j < m;
    };
    for (int i = 0; i < q.size(); i++)
    {
        int x = q[i].first, y = q[i].second;
        for (int k = 0; k < 4; k++)
        {
            int nx = x + cx[k], ny = y + cy[k];
            if (ok(nx, ny) && s[nx][ny] != '#' && wall[nx][ny] > wall[x][y] + 1)
            {
                wall[nx][ny] = wall[x][y] + 1;
                q.push_back({nx, ny});
            }
        }
    }
    typedef pair<int, int> pii;
    set<pair<int, pii> > S;
    S.insert({0, {sx, sy}});
    while (S.size())
    {
        auto it = S.begin();
        int x = (*it).second.first;
        int y = (*it).second.second;
        //cout << x << " " << y << " " << dist[x][y] << endl;
        S.erase(S.begin());
        for (int k = 0; k < 4; k++)
        {
            int nx = x + cx[k], ny = y + cy[k];
            if (ok(nx, ny) && s[nx][ny] != '#' && dist[nx][ny] > dist[x][y] + 1)
            {
                S.erase({dist[nx][ny], {nx, ny}});
                dist[nx][ny] = dist[x][y] + 1;
                S.insert({dist[nx][ny], {nx, ny}});
            }
        }
        {
            int nx = up[x][y], ny = y;
            if (dist[nx][ny] > dist[x][y] + wall[x][y])
            {
                S.erase({dist[nx][ny], {nx, ny}});
                dist[nx][ny] = dist[x][y] + wall[x][y];
                S.insert({dist[nx][ny], {nx, ny}});
            }
        }
        {
            int nx = down[x][y], ny = y;
            if (dist[nx][ny] > dist[x][y] + wall[x][y])
            {
                S.erase({dist[nx][ny], {nx, ny}});
                dist[nx][ny] = dist[x][y] + wall[x][y];
                S.insert({dist[nx][ny], {nx, ny}});
            }
        }
        {
            int nx = x, ny = right[x][y];
            if (dist[nx][ny] > dist[x][y] + wall[x][y])
            {
                S.erase({dist[nx][ny], {nx, ny}});
                dist[nx][ny] = dist[x][y] + wall[x][y];
                S.insert({dist[nx][ny], {nx, ny}});
            }
        }
        {
            int nx = x, ny = left[x][y];
            if (dist[nx][ny] > dist[x][y] + wall[x][y])
            {
                S.erase({dist[nx][ny], {nx, ny}});
                dist[nx][ny] = dist[x][y] + wall[x][y];
                S.insert({dist[nx][ny], {nx, ny}});
            }
        }
    }
    cout << dist[fx][fy];
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:89:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for (int i = 0; i < q.size(); i++)
      |                     ~~^~~~~~~~~~
portals.cpp:76:16: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |     dist[sx][sy] = 0;
      |                ^
portals.cpp:76:12: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |     dist[sx][sy] = 0;
      |            ^
portals.cpp:159:24: warning: 'fy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  159 |     cout << dist[fx][fy];
      |                        ^
portals.cpp:159:20: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  159 |     cout << dist[fx][fy];
      |                    ^

• Subtask 1: 11 / 11
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 30 / 30