[백준] 9205 - 맥주 마시면서 걸어가기(설명X)

#include <cstdio>
#include <queue>
using namespace std;
 
bool bfs(int** arr, int size) {
    bool* visited = new bool[size] { true, };
    queue<int> q;
    q.push(0);
 
    while (!q.empty()) {
        int now = q.front();
        q.pop();
        if (now == size - 1)
            return true;
 
        for (int i = 0; i < size; i++) {
            if (arr[now][i] <= 1000 && !visited[i]) {
                visited[i] = true;
                q.push(i);
            }
        }
    }
    return false;
}
 
int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) {
        int n;
        scanf("%d", &n);
        pair<int, int>* place = new pair<int, int>[n + 2];
        for (int j = 0; j < n + 2; j++)
            scanf("%d %d", &place[j].first, &place[j].second);
 
        int** graph = new int* [n + 2];
        for (int j = 0; j < n + 2; j++) {
            graph[j] = new int[n + 2]{ 0, };
            for (int k = 0; k < n + 2; k++) {
                int disX = place[j].first - place[k].first > 0 ? place[j].first - place[k].first : -(place[j].first - place[k].first);
                int disY = place[j].second - place[k].second > 0 ? place[j].second - place[k].second : -(place[j].second - place[k].second);
                graph[j][k] = disX + disY;
            }
        }
 
        bool isHappy = bfs(graph, n + 2);
        if (isHappy)
            printf("happy\n");
        else
            printf("sad\n");
 
        delete[] place;
        for (int j = 0; j < n + 2; j++)
            delete[] graph[j];
        delete[] graph;
    }
}