11978 Mowing the Field (Bronze)

x,y 위치의 풀을 깎고 나면 t초 후에 다시 깎아야할만큼 자란다.

그리고 FJ는 항상 효율적으로 움직이기 때문에 같은 위치를 t초가 지나기 전에 깎지 않는다.

FJ의 움직임이 N번 주어졌을 때 가능한 t중 최대값을 구하는 문제다.

해법

움직이면서 생기는 교차점이 있으면 교차하는데까지 걸리는 시간을 구하고 이 시간중 최소값을 구하면 된다.

N이 100까지이고 한번 움직이는데 최대 10번 움직이기 때문에 한칸씩 움직이면서 map에 타이밍을 저장한다.

같은 위치를 또 방문한다면 현재시간과 저장된 시간을 비교하고 ans를 갱신한다.

#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
 
map<pair<int, int>, int> s;
 
int main() {
    int n, x = 0, y = 0, cnt = 0, ans = 100000, dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
    scanf("%d", &n);
    s[{x, y}] = 0;
    while (n--) {
        char d;
        int c;
        scanf(" %c %d", &d, &c);
        if (d == 'N') d = 3;
        else if (d == 'E') d = 0;
        else if (d == 'W') d = 1;
        else d = 2;
        while (c--) {
            x += dx[d]; y += dy[d];
            cnt++;
            if (s.count({ x,y })) ans = min(ans, cnt - s[{x, y}]);
            s[{x, y}] = cnt;
        }
    }
    printf("%d\n", ans == 100000 ? -1 : ans);
    return 0;
}