USACO2020DEC Question 3 (Stuck in a Rut) Solution

Title
Title Description
Farmer John has recently expanded his farm, which is almost infinite from the cows’ point of view! The cows think of the grazing area on the farm as an infinite two-dimensional square of squares, each with delicious grass (think of each square as a square on a chessboard) ). Farmer John’s N cows (1≤N≤50) are initially located in different squares, some facing north and some facing east.
Every hour, each cow will do one of the following:
If the grass in the square she is currently in has been eaten by other cows, she will stop.
Eat all the grass in the square she is currently on and move one square in the direction she is facing.
After a period of time, a trail of gnawed baldness is left behind each cow.
If two cows move to the same square with grass in one move, they share the grass in that square and continue to move in the direction they are facing for the next hour.
Request the amount of grass eaten by each cow. Some cows never stop, thus eating an infinite amount of grass.
Input
The first line of input contains N. The following N lines, each describing the starting position of a cow, contains a character N (for facing north) or E (for facing east), and two non-negative integers x and y (0≤x≤109, 0≤ y≤109) represents the coordinates of the square. All x-coordinates are different, and all y-coordinates are different.
To make the directions and coordinates as clear as possible, if a cow is at square (x,y) and moves north, she will reach square (x,y+1). If she moves east, she will reach square (x+1,y).
output
Output N lines. The ith row of the output contains the number of squares that the ith cow in the input ate grass. If a cow can eat an infinite amount of grass, output “Infinity” for that cow.
sample input
6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 2
N 8
1Sample output
5
3
Infinity
Infinity
2
8
5Problem –
solving ideas
Simulate according to the meaning of the problem. Every time you take out the top of the heap, move the cow on the top of the heap one square in its direction, and judge whether the cow after the move is blocked. If the current cow is blocked, record who is blocking the cow. Calculate the coordinates of the next square where the cow moves forward, and if it exceeds the map range, don’t put the cow back in (that is, it will never be blocked). Otherwise, calculate the time required to advance to the next grid, add the current time, and put it back in.
Reference Code

#include<bits/stdc++.h>
using namespace std;
const int N = 105, inf = 0x3f3f3f3f;
typedef long long ll;
struct node {
    int stop, x, y; char opt;
} a[N];
int n, tmp[N];
int hit(int x, int y, int now) {
    node i = a[x], j = a[y];
    if (i.opt == j.opt) {
        return inf;
    }
    if (i.opt == 'E') {
        swap(i.x, i.y); swap(j.x, j.y);
    }
    if (j.y <= i.y) {
        return inf;
    }
    if (j.stop == inf) {
        if (i.x < j.x - now || i.x >= j.x + j.y - i.y) {
            return inf;
        }
    } else {
        if (i.x > j.x || i.x < j.x - j.stop) {
            return inf;
        }
    }
    return now + j.y - i.y;
}
int move(int now) {
    int minn = inf; memset(tmp, 0, sizeof tmp);
    for (int i = 1; i <= n; ++i) {
        tmp[i] = inf;
        if (a[i].stop == inf) {
            for (int j = 1; j <= n; ++j) {
                tmp[i] = min(tmp[i], hit(i, j, now));
            }
            from = who(from, tmp[i]);
        }
    }
    if (minn == inf) {
        return inf;
    }
    for (int i = 1; i <= n; ++i) {
        if (a[i].stop == inf) {
            if (a[i].opt == 'N') {
                a[i].y += (minn - now);
            } else {
                a[i].x += (minn - now);
            }
        }
        if (tmp[i] == minn) {
            a[i].stop = minn;
        }
    }
    return from;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].opt >> a[i].x >> a[i].y;
        a[i].stop = inf;
    }
    int now = 0;
    do {
        now = move(now);
    } while (now != inf);
    for (int i = 1; i <= n; ++i) {
        if (a[i].stop == inf) {
            cout << "Infinity\n";
        } else {
            cout << a[i].stop << '\n';
        }
    }
    return 0;
}

Leave a Comment

Your email address will not be published. Required fields are marked *