3349. 최솟값으로 이동하기

3349. 최솟값으로 이동하기

처음에는 BFS를 삼차원배열로 풀었더니 런타임에러...

그래서 생각해보니, 그냥 좌표값만을 가지고 충분히 거리를 구할 수 있었다.

(x1,y1)->(x2,y2) 로 이동한다고 했을 때 , (x2-x1)*(y2-y1) 이 양수라면, 이는 북동 혹은 남서로 이동하므로, 지름길을 사용할 수 있게 된다.

따라서 그런 경우에 따라서 나누면, 좌표값만을 가지고 충분히 거리를 구할 수 있게 된다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int h, w, n,ans=0;
        cin >> h >> w >> n;
        vector<pair<int, int>> v(n);
        for (int i = 0; i < n; i++)
        {
            cin >> v[i].first >> v[i].second;
        }
 
        for (int i = 0; i < n-1; i++)
        {
            int x1 = v[i].first, y1 = v[i].second;
            int x2 = v[i + 1].first, y2 = v[i + 1].second;
            int X = x2 - x1;
            int Y = y2 - y1;
            if (X*Y > 0)
            {
                if (abs(X) > abs(Y))
                {
                    ans += abs(Y)+ (abs(X) - abs(Y));
                }
                else
                {
                    ans += abs(X)+ (abs(Y) - abs(X));
                }
 
            }
            else
            {
                ans += (abs(X) + abs(Y));
            }
 
        }
 
        cout << "#" << t << " " << ans << "\n";
    }
 
    return 0;
}