Submission #675277

#	Time	Username	Problem	Language	Result	Execution time	Memory
675277		vjudge1	Portals (BOI14_portals)	C++17	100 / 100	312 ms	9856 KiB

portals

#include<bits/stdc++.h>
#define task "A"
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
using namespace std;
const int maxN = 1e3 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int m, n;
string a[maxN];
pair<int, int> s, t;
int d[maxN][maxN];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<int> hang[maxN], cot[maxN];

struct TPQRect
{
    int x, y, dlab;
    bool operator < (const TPQRect& other) const
    {
        return other.dlab < dlab;
    }
    bool Valid() const
    {
        return d[x][y] == dlab;
    }
};

void Input()
{
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
    {
        hang[i].pb(0);
        hang[i].pb(n + 1);
    }
    for(int i = 1; i <= n; i++)
    {
        cot[i].pb(0);
        cot[i].pb(m + 1);
    }
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i];
        a[i] = ' ' + a[i];
        for(int j = 1; j <= n; j++)
        {
            if(a[i][j] == 'S')
                s = {i, j};
            if(a[i][j] == 'C')
                t = {i, j};
            if(a[i][j] == '#')
            {
                hang[i].pb(j);
                cot[j].pb(i);
            }
        }
    }
    for(int i = 1; i <= m; i++)
        sort(hang[i].begin(), hang[i].end());
    for(int i = 1; i <= n; i++)
        sort(cot[i].begin(), cot[i].end());
}

void Dijkstra()
{
    priority_queue<TPQRect> pq;
    memset(d, 3, sizeof d);
    d[s.fi][s.se] = 0;
    pq.push({s.fi, s.se, 0});
    while(!pq.empty())
    {
        TPQRect R = pq.top();
        pq.pop();
        if(!R.Valid())
            continue;
        int x = R.x, y = R.y;
        for(int i=0; i<4; i++)
        {
            int u = x + dx[i], v = y + dy[i];
            if(u < 1 || u > m || v < 1 || v > n || a[u][v] == '#')
                continue;
            if(d[u][v] > d[x][y] + 1)
            {
                d[u][v] = d[x][y] + 1;
                pq.push({u, v, d[u][v]});
            }
        }
        vector<pii> vc;
        int id = lower_bound(hang[x].begin(), hang[x].end(), y) - hang[x].begin();
        vc.pb({x, hang[x][id] - 1});
        id--;
        vc.pb({x, hang[x][id] + 1});
        id = lower_bound(cot[y].begin(), cot[y].end(), x) - cot[y].begin();
        vc.pb({cot[y][id] - 1, y});
        id--;
        vc.pb({cot[y][id] + 1, y});
        for(int i=0; i<4; i++)
            for(int j=0; j<4; j++)
            {
                int w = abs(x - vc[j].fi) + abs(y - vc[j].se) + 1;
                if(d[vc[i].fi][vc[i].se] > d[x][y] + w)
                {
                    d[vc[i].fi][vc[i].se] = d[x][y] + w;
                    pq.push({vc[i].fi, vc[i].se, d[vc[i].fi][vc[i].se]});
                }
            }
    }
}

void Solve()
{
    Dijkstra();
    cout << d[t.fi][t.se];
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    if (fopen(task".INP","r"))
    {
        freopen(task".INP","r",stdin);
        freopen(task".OUT","w",stdout);
    }
    Input();
    Solve();
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:128:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
portals.cpp:129:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |         freopen(task".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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