Submission #93234

#	Time	Username	Problem	Language	Result	Execution time	Memory
93234		Alexa2001	Golf (JOI17_golf)	C++17	30 / 100	1502 ms	79564 KiB

golf

#include <bits/stdc++.h>

using namespace std;

const int Nmax = 2010;

map<int,int> mpx, mpy;
int X1, X2, Y1, Y2, n, N, M;

int dist[Nmax][Nmax][4];
int a[Nmax], b[Nmax], c[Nmax], d[Nmax], mat[Nmax][Nmax];
int i, j;
bool blocked[Nmax][Nmax][4];

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

struct state
{
    int x, y, dir;
};

int solve()
{
    queue<state> q;

    q.push({X1, Y1, 0});
    q.push({X1, Y1, 1});
    q.push({X1, Y1, 2});
    q.push({X1, Y1, 3});

    int x, y, dir, i, X, Y, Dist;

    for(x=1; x<=N; ++x)
        for(y=1; y<=M; ++y)
            for(dir=0; dir<4; ++dir)
                dist[x][y][dir] = ((x==X1 && y==Y1) ? 0 : 10 * Nmax);

    while(q.size())
    {
        x = q.front().x;
        y = q.front().y;
        dir = q.front().dir;
        q.pop();

        for(i=0; i<4; ++i)
        {
            X = x + dx[i];
            Y = y + dy[i];
            Dist = dist[x][y][dir] + (i != dir);

            if(dist[X][Y][i] > Dist && !blocked[X][Y][i])
            {
                dist[X][Y][i] = Dist;
                q.push({X, Y, i});
            }
        }
    }

    int ans = 10 * Nmax;
    for(i=0; i<4; ++i)
        ans = min(ans, dist[X2][Y2][i]);
    return ans;
}

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

    cin >> X1 >> Y1 >> X2 >> Y2;
    cin >> n;
    mpx[X1] = mpx[X2] = mpy[Y1] = mpy[Y2] = 1;

    int i;
    for(i=1; i<=n; ++i)
    {
        cin >> a[i] >> c[i] >> b[i] >> d[i];
        mpx[a[i]] = mpx[c[i]] = mpy[b[i]] = mpy[d[i]] = 1;
    }

    for(auto &it : mpx) it.second = ++N;
    for(auto &it : mpy) it.second = ++M;

    X1 = mpx[X1]; X2 = mpx[X2];
    Y1 = mpy[Y1]; Y2 = mpy[Y2];

    for(i=1; i<=n; ++i)
    {
        a[i] = mpx[a[i]];
        b[i] = mpy[b[i]];
        c[i] = mpx[c[i]];
        d[i] = mpy[d[i]];
    }

    for(i=1; i<=n; ++i)
    {
        for(j=a[i]+1; j<=c[i]-1; ++j) blocked[j][b[i]+1][1] = blocked[j][d[i]-1][0] = 1;
        for(j=b[i]+1; j<=d[i]-1; ++j) blocked[a[i]+1][j][3] = blocked[c[i]-1][j][2] = 1;
    }

    cout << solve() + 1 << '\n';
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 0 / 70