Submission #693251

#	Time	Username	Problem	Language	Result	Execution time	Memory
693251		Tien_Noob	Portals (BOI14_portals)	C++17	100 / 100	204 ms	22208 KiB

portals

//Make CSP great again
//Vengeance
#include <bits/stdc++.h>
#define TASK "TESTCODE"
using namespace std;
const int N = 1e3 + 1;
int d[N + 1][N + 1];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
char a[N + 1][N + 1];
int up[N + 1][N + 1], dw[N + 1][N + 1], rt[N + 1][N + 1], lt[N + 1][N + 1];
int n, m;
pair<int, int> fn;
struct TPQItem
{
    int dlab, x, y;
    bool operator < (const TPQItem &other) const
    {
        return other.dlab < dlab;
    }
};
priority_queue<TPQItem> PQ;
void read()
{
    cin >> n >> m;
    memset(up, -1, sizeof(up));
    memset(dw, -1, sizeof(dw));
    memset(rt, -1, sizeof(rt));
    memset(lt, -1, sizeof(lt));
    memset(d, 0x3f, sizeof(d));
    for (int i = 1; i <= n; ++ i)
    {
        for (int j = 1; j <= m; ++ j)
        {
            cin >> a[i][j];
            if (a[i][j] != '#')
            {
                up[i][j] = up[i - 1][j] + 1;
                lt[i][j] = lt[i][j - 1] + 1;
            }
            if (a[i][j] == 'S')
            {
                PQ.push({0, i, j});
                d[i][j] = 0;
            }
            if (a[i][j] == 'C')
            {
                fn = {i, j};
            }
        }
    }
}
int occho(int t, int i, int j)
{
    if (t == 0)
    {
        return up[i][j];
    }
    if (t == 1)
    {
        return rt[i][j];
    }
    if (t == 2)
    {
        return dw[i][j];
    }
    if (t == 3)
    {
        return lt[i][j];
    }
}
void solve()
{
    for (int i = n; i >= 1; -- i)
    {
        for (int j = m; j >= 1; -- j)
        {
            if (a[i][j] != '#')
            {
                dw[i][j] = dw[i + 1][j] + 1;
                rt[i][j] = rt[i][j + 1] + 1;
            }
        }
    }
    while(!PQ.empty())
    {
        TPQItem p = PQ.top();
        PQ.pop();
        int x = p.x, y = p.y;
        if (d[x][y] != p.dlab)
        {
            continue;
        }
        for (int k = 0; k < 4; ++ k)
        {
            int i = x + dx[k], j = y + dy[k];
            if (i < 1 || i > n || j < 1 || j > m || a[i][j] == '#')
            {
                continue;
            }
            if (d[i][j] > d[x][y] + 1)
            {
                d[i][j] = d[x][y] + 1;
                PQ.push({d[i][j], i, j});
            }
        }
        int walk = 1e9;
        for (int i = 0; i < 4; ++ i)
        {
            walk = min(walk, occho(i, x, y));
        }
        for (int k = 0; k < 4; ++ k)
        {
            int i = x + dx[k] * occho(k, x, y), j = y + dy[k] * occho(k, x, y);
            /*if (x == 4 && y == 3)
            {
                cerr << i << ' ' << j << ' ' << walk + 1 << '\n';
            }*/
            if (i < 1 || i > n || j < 1 || j > m || a[i][j] == '#')
            {
                continue;
            }
            if (d[i][j] > d[x][y] + walk + 1)
            {
                d[i][j] = d[x][y] + walk + 1;
                PQ.push({d[i][j], i, j});
            }
        }
    }
    cout << d[fn.first][fn.second];
}
int 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);
    }
    int t = 1;
    bool typetest = false;
    if (typetest)
    {
        cin >> t;
    }
    for (int __ = 1; __ <= t; ++ __)
    {
        //cout << "Case " << __ << ": ";
        read();
        solve();
    }
}

Compilation message (stderr)

portals.cpp: In function 'int occho(int, int, int)':
portals.cpp:71:1: warning: control reaches end of non-void function [-Wreturn-type]
   71 | }
      | ^
portals.cpp: In function 'int main()':
portals.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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