거북이


작성일 : 2017-01-17 00:51:09
조회수 : 466



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


거북이가 0,0 의 위치에서 북쪽을 보고 있다고 하였으므로 실제로 좌표와 방향을 지정한 뒤, 명령어를 처리합니다. $i$번째 명령어를 처리하였을 때의 좌표를 $x_i$, $y_i$ 라고 한다면, 이 점을 모두 포함하는 사각형의 왼쪽 아래 꼭지점의 좌표는 나왔던 값들 중 가장 작은 값에 해당됩니다. 반대로, 오른쪽 위의 꼭지점의 좌표는 가장 큰 값에 해당 되겠죠? 이를 통해 사각형의 넓이를 구하면 다음과 같습니다.


$area = (max(x_i)-min(x_i)) * (max(y_i) - min(y_i))$

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
    int T;

    cin >> T;
    while (T--)
    {
        string s;
        int x = 0, y = 0, sx = 0, sy = 0, ex = 0, ey = 0;
        int xdir[4] = { 0,1,0,-1 }, ydir[4] = { 1,0,-1,0 }, p = 0;

        cin >> s;
        for (char c : s)
        {
            if (c == 'F') x += xdir[p], y += ydir[p];
            else if (c == 'B') x -= xdir[p], y -= ydir[p];
            else if (c == 'R') p++;
            else p--;
            if (p > 3) p = 0;
            else if (p < 0) p = 3;
            sx = min(sx, x);
            sy = min(sy, y);
            ex = max(ex, x);
            ey = max(ey, y);
        }
        int w = abs(ex - sx), h = abs(ey - sy);
        cout << w*h << "\n";
    }
}

거북이 - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글