Submission #98416

#	Time	Username	Problem	Language	Result	Execution time	Memory
98416		Kastanda	Portals (BOI14_portals)	C++11	100 / 100	457 ms	30388 KiB

portals

#include<bits/stdc++.h>
using namespace std;
const int N = 1009;
int n, m, D[N][N], F[N][N], qu[N * N];
int up[N][N], dn[N][N], le[N][N], ri[N][N];
int gx[] = {-1, 1, 0, 0}, gy[] = {0, 0, -1, 1};
char A[N][N];
priority_queue < pair < int , int > > Pq;
inline void Relax(int i, int j, int w)
{
    if (A[i][j] == '.' && D[i][j] > w)
    {
        D[i][j] = w;
        Pq.push({-D[i][j], i * N + j});
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", &A[i][1]);
    pair < int , int > st, en;
    memset(F, 63, sizeof(F));
    int l = 0, r = 0;
    for (int i = 0; i <= n + 1; i++)
        for (int j = 0; j <= m + 1; j++)
        {
            if (A[i][j] == 'S')
                st = {i, j}, A[i][j] = '.';
            else if (A[i][j] == 'C')
                en = {i, j}, A[i][j] = '.';
            else if (A[i][j] != '.')
                F[i][j] = 0, qu[r ++] = i * N + j;
        }
    while (r - l)
    {
        int i = qu[l] / N, j = qu[l ++] % N;
        for (int h = 0; h < 4; h ++)
        {
            int tx = i + gx[h], ty = j + gy[h];
            if (tx >= 1 && tx <= n && ty >= 1 && ty <= m)
                if (F[tx][ty] > F[i][j] + 1)
                    F[tx][ty] = F[i][j] + 1, qu[r ++] = tx * N + ty;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            le[i][j] = (A[i][j] == '#') ? (0) : (le[i][j - 1] + 1);
        for (int j = m; j; j --)
            ri[i][j] = (A[i][j] == '#') ? (0) : (ri[i][j + 1] + 1);
    }
    for (int j = 1; j <= m; j++)
    {
        for (int i = 1; i <= n; i++)
            up[i][j] = (A[i][j] == '#') ? (0) : (up[i - 1][j] + 1);
        for (int i = n; i; i--)
            dn[i][j] = (A[i][j] == '#') ? (0) : (dn[i + 1][j] + 1);
    }
    memset(D, 63, sizeof(D));
    D[st.first][st.second] = 0;
    Pq.push({0, st.first * N + st.second});
    while (Pq.size())
    {
        int i = Pq.top().second / N, j = Pq.top().second % N;
        int d = - Pq.top().first; Pq.pop();
        if (d > D[i][j]) continue;
        for (int h = 0; h < 4; h ++)
            Relax(i + gx[h], j + gy[h], D[i][j] + 1);
        Relax(i, j - le[i][j] + 1, D[i][j] + F[i][j]);
        Relax(i, j + ri[i][j] - 1, D[i][j] + F[i][j]);
        Relax(i - up[i][j] + 1, j, D[i][j] + F[i][j]);
        Relax(i + dn[i][j] - 1, j, D[i][j] + F[i][j]);
    }
    return !printf("%d\n", D[en.first][en.second]);
}

Compilation message (stderr)

portals.cpp: In function 'int main()':
portals.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
portals.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%s", &A[i][1]);
         ~~~~~^~~~~~~~~~~~~~~~

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