Submission #288226

#	Time	Username	Problem	Language	Result	Execution time	Memory
288226		Alexa2001	Dangerous Skating (JOI16_skating)	C++17	100 / 100	332 ms	110200 KiB

skating

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 1005, Nodes = 3 * Nmax * Nmax, inf = 1e9;

int dx[] = {0, 0, +1, -1};
int dy[] = {-1, +1, 0, 0};


int n, m, nr;
char A[Nmax][Nmax];
int startX, startY, finishX, finishY;
int dist[Nodes];
bool used[Nodes];
int hor[Nmax][Nmax], ver[Nmax][Nmax];

queue<int> q[3];
vector<int> to[Nodes];


int code(int x, int y)
{
    return (x-1) * m + y;
}




void prepare()
{
    int i, j;

    nr = n * m;

    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            if(A[i][j] == '.')
            {
                if(A[i][j-1] == '.') hor[i][j] = hor[i][j-1];
                    else hor[i][j] = ++nr;

                if(A[i-1][j] == '.') ver[i][j] = ver[i-1][j];
                    else ver[i][j] = ++nr;
            }
    for(i=1; i<=n; ++i)
        for(j=1; j<=m; ++j)
            if(A[i][j] == '#')
            {
                if(A[i-1][j] == '.') to[ver[i-1][j]].push_back(code(i-1, j));
                if(A[i+1][j] == '.') to[ver[i+1][j]].push_back(code(i+1, j));

                if(A[i][j-1] == '.') to[hor[i][j-1]].push_back(code(i, j-1));
                if(A[i][j+1] == '.') to[hor[i][j+1]].push_back(code(i, j+1));
            }
}

void add1(int node)
{
    int x, y;
    if(node % m == 0) x = node / m, y = m;
        else x = node / m + 1, y = node % m;

    for(int i=0; i<4; ++i)
    {
        int nx = x + dx[i], ny = y + dy[i];
        if(A[nx][ny] != '.') continue;

        int c = code(nx, ny);

        if(dist[c] > dist[node] + 2)
        {
            dist[c] = dist[node] + 2;
            q[2].push(c);
        }
    }

    if(dist[hor[x][y]] > dist[node])
    {
        dist[hor[x][y]] = dist[node];
        q[0].push(hor[x][y]);
    }

    if(dist[ver[x][y]] > dist[node])
    {
        dist[ver[x][y]] = dist[node];
        q[0].push(ver[x][y]);
    }
}

void add2(int node)
{
    for(auto it : to[node])
        if(dist[it] > dist[node] + 1)
        {
            dist[it] = dist[node] + 1;
            q[1].push(it);
        }
}

int find_next()
{
    int i;
    for(i=0; i<=2; ++i)
        while(q[i].size() && used[q[i].front()]) q[i].pop();

    int mn = inf, x = -1, id;
    for(i=0; i<=2; ++i)
        if(q[i].size() && dist[q[i].front()] < mn)
            mn = dist[q[i].front()], x = q[i].front(), id = i;

    if(mn == inf) return -1;
    q[id].pop();
    return x;
}

int solve()
{
    int i;
    for(i=1; i<=nr; ++i) dist[i] = inf;

    q[0].push(code(startX, startY));
    dist[code(startX, startY)] = 0;

    while(1)
    {
        int node = find_next();
        if(node == -1) break;
        used[node] = 1;

        if(node <= n * m) add1(node);
            else add2(node);
    }

    return (dist[code(finishX, finishY)] == inf ? -1 : dist[code(finishX, finishY)]);
}

int main()
{
  //  freopen("input", "r", stdin);
    cin.tie(0); cin.sync_with_stdio(false);

    cin >> n >> m;

    int i;
    for(i=1; i<=n; ++i) cin >> (A[i] + 1);

    cin >> startX >> startY;
    cin >> finishX >> finishY;

    prepare();
    cout << solve() << '\n';

    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 65 / 65
• Subtask 3: 22 / 22