Submission #330069

#	Time	Username	Problem	Language	Result	Execution time	Memory
330069		IgorI	Portals (BOI14_portals)	C++17	20 / 100	4 ms	1644 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));
    dist[sx][sy] = 0;
    vector<pair<int, int> > q = {{sx, sy}};
    for (int i = 0; i < q.size(); i++)
    {
        int x = q[i].first, y = q[i].second;
        //cout << x << " " << y << endl;
        //cout << s[x][y] << endl;
        for (int k = 0; k < 4; k++)
        {
            int nx = x + cx[k], ny = y + cy[k];
            if (s[nx][ny] != '#' && dist[nx][ny] > dist[x][y] + 1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.push_back({nx, ny});
            }
        }
        {
            int nx = x, ny = left[x][y];
            if (dist[nx][ny] > dist[x][y] + 1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.push_back({nx, ny});
            }
        }
        {
            int nx = x, ny = right[x][y];
            if (dist[nx][ny] > dist[x][y] + 1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.push_back({nx, ny});
            }
        }
        {
            int nx = up[x][y], ny = y;
            if (dist[nx][ny] > dist[x][y] + 1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.push_back({nx, ny});
            }
        }
        {
            int nx = down[x][y], ny = y;
            if (dist[nx][ny] > dist[x][y] + 1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.push_back({nx, ny});
            }
        }
    }
    cout << dist[fx][fy];
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:77: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]
   77 |     for (int i = 0; i < q.size(); i++)
      |                     ~~^~~~~~~~~~
portals.cpp:64:13: warning: 'sy' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     int sx, sy, fx, fy;
      |             ^~
portals.cpp:64:9: warning: 'sx' may be used uninitialized in this function [-Wmaybe-uninitialized]
   64 |     int sx, sy, fx, fy;
      |         ^~
portals.cpp:124:24: warning: 'fy' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |     cout << dist[fx][fy];
      |                        ^
portals.cpp:124:20: warning: 'fx' may be used uninitialized in this function [-Wmaybe-uninitialized]
  124 |     cout << dist[fx][fy];
      |                    ^

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